KMP 算法 java实现
我的Java代码实现
package jj4_6; public class KMP { public static boolean contains(String a,String b){ /* * 第一步,对b字符串做一个预处理 */ Integer[] fuzhu = new Integer[b.length()]; for(Integer i= 0;i<b.length();i++){ // i == 3 时 // nowstr = "abab" String nowstr =b.substring(0, i+1); fuzhu[i] = 0; for(Integer j =i;j>0;j--){ // left = "aba" String left = nowstr.substring(0,j); // right = "bab"; String right = nowstr.substring(i-j+1, nowstr.length()); if( left.equals(right) ){ fuzhu[i] = j; break; } } } /* * 完成匹配 */ for(Integer i = 0;i <= a.length()-b.length();){ Integer j; for(j =0;j<b.length();j++){ if(a.charAt(i+j) != b.charAt(j)){ /* * 计算i的移动距离 */ if(j==0) i++; else i = i + ( (j-1) + 1 - fuzhu[(j-1)]); /* * 重新开始匹配 */ break; } } if(j == b.length()) return true; } return false; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。