KMP匹配算法
程序员文章站
2024-02-26 22:23:46
...
KMP中next数组的求法,及kmp的完整代码,以及kmp的算法理解。
朴素匹配算法改进得到KMP算法。
如果我们知道T中'a'与T中后面的字符均不相等,而且T串的第二位'b'与S串中第二位'b'已经判断相等,那T中的首位'a'和S串第二位时可以不用再去判断了,他们是绝对不可能相等的。
T[0] !=T[1] && T[1] == S[1] ---> T[0]!=S[1]
举个栗子,完整分析
主串S = "abcababca" 子串T="abcabx"(从下标1开始)
第一步:前5个字符完全相等,第6个不相等,根据文章开头说的,T的首字母和后面第2、3位字符俊不等,那么S[2],S[3],和T[1]肯定不会相等,那么朴素算法的②③步都是多余的。
第二步:T[1]与T[4]的'a'字符,T[2]与T[5]的'b'字符是相同的,在①的时候,T[4],T[5]就已经和S[4],S[5]比较过,是相等的,那我们可以断定T[1],T[2]和S[4],S[5]肯定也是相等的,那么④⑤这两步也是可以省略的。
那就只剩下:
原本(朴素匹配)我们在①时,i=6,i值经过2,3,4,5变化,到⑥i值又回到6。但是上面一张图,i值是不回溯的,只有j值在变。
而j值也只在 子串T的首字符与自身后面字符相同的时候才会发生变化,与主串变化无关。
求next的数组值需要了解一下前后缀,求next值就是利用前后缀的相似度。
栗子分析
完整代码
代码与上图的函数式有点区别:
next[0] = -1;
其他情况等于 0;
相等的时候,next值为前后缀的相同字符数。
public class KMP {
private String str; //主串
private String subStr; //子串
private int[] next; //子串的next数组
public KMP(String str,String subStr){
this.str = str;
this.subStr = subStr;
next = getNextValue();
}
//获得子串的next数组
public int[] getNextValue(){
int len = subStr.length();
int[] result = new int[len];
int i=0,j=-1; //i代表后缀,j代表前缀。
result[0] = -1;
while(i<len-1) {
//如果前缀与后缀相等,next[j+1] = next[j] + 1
if(j==-1 || subStr.charAt(i) == subStr.charAt(j)) {
++i;
++j;
result[i] = j;
} else {
//前缀与后缀不相等,j回溯,
j = result[j];
}
}
return result;
}
//匹配
public int kmp() {
int startIndex = -1; //匹配到子串的下标
int slen = str.length(); //主串长度
int subLen = subStr.length(); //子串长度
int i=0,j=0;
while(i<slen-1){
//当j=-1时,代表着匹配的第一个字符
if(j==-1 || str.charAt(i)==subStr.charAt(j)){
++i;
++j;
}else{
//不相等,直接回溯到合适的位置,主串i值保持不变,而不是朴素匹配的一步步回溯。
j = next[j];
}
//子串从下标0开始与子串匹配,j等于子串长度,代表找到了匹配串
if(j == subLen-1){
startIndex = i-subLen+1;
break;
}
}
return startIndex;
}
public static void main(String[] args) {
KMP kmp = new KMP("goodgoole","goole");
for(int i=0;i<kmp.next.length;i++){
System.out.print(kmp.next[i]);
}
int index = kmp.kmp();
System.out.println("startIndex:" + index);
}
}
上一篇: php阳历转农历优化版
下一篇: 路由守卫