newBM.rar_Boyer Moore_Boyer-Moore算法_boyer

package project; public class newBM { int count = 0; int[] computeBMBc(String P){ int CHARSET = 65536; int[] bmBc = new int[CHARSET]; int m = P.length(); for(int i = 0;i < 65536;i++) bmBc[i] = m; for(int i = 0;i < m-1;i++) bmBc[(int)P.charAt(i)] = m - i -1; return bmBc; }//应该正确 int[] computeBMGs(String P){ int m = P.length(); int[] bmGs = new int[m]; int[] Rsuff = computeRsuff(P); for(int i = 0;i<m;i++) bmGs[i]=m; int j = 0; for(int i = m -2;i>=0;i--){ if(Rsuff[i]==i+1) while(j<=m-i-2){ if(bmGs[j]==m) bmGs[j]=m-i-1; j = j+1; } } for(int i=0;i<m-1;i++) bmGs[m-Rsuff[i]-1]=m-i-1;// right return bmGs; } int[] computeRsuff(String P){ int m = P.length(); int[] Rsuff = new int[m]; Rsuff[m-1] = m;// 是否为m?yes for(int i = m-2;i>0;i--){ int j = i; int k = m-1; while(P.charAt(j)==P.charAt(k)){ if(j==0) break; if(j>0){ j--; k--; } } if(i==j){ Rsuff[i]=0; } else Rsuff[i] = i-j; } if(P.charAt(0)==P.charAt(m-1)) Rsuff[0]=1; return Rsuff; } void BM_Matcher(String P,String T){ int n = T.length(); int m = P.length(); int[] bmBc = computeBMBc(P); int[] bmGs = computeBMGs(P); int s = 0; while(s<=n-m){ int i = m-1; while(P.charAt(i)==T.charAt(s+i)){ count++; if(i==0){ System.out.println("Pattern occurs with shift " + s); s = s + java.lang.Math.max(bmGs[i], bmBc[(int)T.charAt(s+i)-m+i+1]); }else i = i-1;//这个地方有问题呀 孩子 } count++; if(i>0) s = s + java.lang.Math.max(bmGs[i], bmBc[(int)T.charAt(s+i)-m+i+1]); } } public static void main(String[] args){ String T = "abcdabheabhiacgabcde"; String p = "bc"; newBM bm = new newBM(); bm.BM_Matcher(p, T); System.out.println("there is " + bm.count + " time matches"); } }