Boyer-Moore算法java实现
2018-07-20 来源:open-open
import java.util.*; public class BoyerMoore { public static void main(String[] args) { String text="中国是一个伟大的国度;伟大的祖国啊"; String pattern="伟大的国度"; BoyerMoore bm=new BoyerMoore(); bm.boyerMoore(pattern, text); } private void preBmBc(String pattern,int patLength,Map<String,Integer> bmBc) { System.out.println("bmbc start process..."); for(int i=patLength-2;i>=0;i--) { if(!bmBc.containsKey(String.valueOf(pattern.charAt(i)))) { bmBc.put(String.valueOf(pattern.charAt(i)),(Integer)(patLength-i-1)); } } } private void suffix(String pattern,int patLength,int [] suffix) { suffix[patLength-1]=patLength; int q=0; for(int i=patLength-2;i>=0;i--) { q=i; while(q>=0&&pattern.charAt(q)==pattern.charAt(patLength-1-i+q)) { q--; } suffix[i]=i-q; } } private void preBmGs(String pattern,int patLength,int []bmGs) { int i,j; int []suffix=new int[patLength]; suffix(pattern,patLength,suffix); //模式串中没有子串匹配上好后缀,也找不到一个最大前缀 for(i=0;i<patLength;i++) { bmGs[i]=patLength; } //模式串中没有子串匹配上好后缀,但找到一个最大前缀 j=0; for(i=patLength-1;i>=0;i--) { if(suffix[i]==i+1) { for(;j<patLength-1-i;j++) { if(bmGs[j]==patLength) { bmGs[j]=patLength-1-i; } } } } //模式串中有子串匹配上好后缀 for(i=0;i<patLength-1;i++) { bmGs[patLength-1-suffix[i]]=patLength-1-i; } System.out.print("bmGs:"); for(i=0;i<patLength;i++) { System.out.print(bmGs[i]+","); } System.out.println(); } private int getBmBc(String c,Map<String,Integer> bmBc,int m) { //如果在规则中则返回相应的值,否则返回pattern的长度 if(bmBc.containsKey(c)) { return bmBc.get(c); }else { return m; } } public void boyerMoore(String pattern,String text ) { int m=pattern.length(); int n=text.length(); Map<String,Integer> bmBc=new HashMap<String,Integer>(); int[] bmGs=new int[m]; //proprocessing preBmBc(pattern,m,bmBc); preBmGs(pattern,m,bmGs); //searching int j=0; int i=0; int count=0; while(j<=n-m) { for(i=m-1;i>=0&&pattern.charAt(i)==text.charAt(i+j);i--) { //用于计数 count++; } if(i<0){ System.out.println("one position is:"+j); j+=bmGs[0]; }else{ j+=Math.max(bmGs[i],getBmBc(String.valueOf(text.charAt(i+j)),bmBc,m)-m+1+i); } } System.out.println("count:"+count); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点!
本站所提供的图片等素材,版权归原作者所有,如需使用,请与原作者联系。
上一篇:C#模拟网络POST请求
下一篇:C#压缩图片算法
最新资讯
热门推荐