分析

KMP是求字符串匹配的算法，由大牛克努特，莫里斯，普莱特于1977年提出，之前好像还有一个MP算法，想了解的朋友可以去网上查一下资料。

对于字符串匹配 设主串T(t1,t2…tm) 检索子串P（p1,p2,…pn) 初学者的第一思路应该是从两个字符串的第一个字符开始比，如果相同，两个字符数组的下标同时加1，不同的话，主串的下标加1，模式串的下标归为1,因为每次比较一旦失败，模式串下标都要回溯，这样子的时间复杂度是O((n-m)* m)。由此，便考虑是否存在一种匹配方式，使得在主串中查找模式串时，匹配失败子串不必回溯，这样可以大大提高效率。KMP算法应运而生，它使用了一个Nest数组来储存模式串中每个字符的最大匹配程度。

举个栗子：

字符数组为 c a c a b c a
Next [i] : -1 0 0 1 2 0 1

其中下标为0的地方默认为-1，方便运算 后面的每一个值为它及自己前面的字符与开头的字符匹配的最大长度 放出公式：Next[i]=Max(k)
k满足 p1p2…p(k-1) == p(i-k+1)p(i-k+2)…p(i-1)

求得Next数组以后，在匹配过程中遇到匹配失败的情况时，另主串不动，模式串下标移动到它的Next数组的值处， 即另j=Next[j], 继续匹配。

证明一下:当P[k]处失配时，P[1]P[2]…P[k-1] == t[j-k+1]t[j-k+2]…t[j-1]

z满足： P[1]P[2]…P[z-1] == P[k-z+1]P[k-z+2]…P[k-1]

只要找到z值,另P的下标转换为z即可继续进行匹配
由于Next数组已经求出模式串P的最大匹配程度，这个z值便是我们所求的Next的数组的值，是不是感觉很奇妙呀~~~

贴上代码

求Nexts数组

1
2
3
4
5
6
7
8
9
10
11
12
13
void getNext(char *p,int *next){
	Next[0]=-1;
	int i=0,j=-1;
	while(i<strlen(p)){
		if(j==-1 || p[i]==p[j]){
			i++;
			j++;;
			next[i]=j;
		}
		else
		j=next[j];
	}
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int KMP(char *t,char *p){
	int i=0;
	int j=0;
	int tl=strlen(t),pl=strlen(p);
//	cout<<strlen(t)<<' '<<strlen(p)<<endl;
	while(i<tl && j<pl) {
		if(j==-1 || t[i]==p[j]){
			i++;
			j++;
		}
		else
			j=Next[j];
	}
//	cout<<i<<' '<<j<<endl;
	if(j==strlen(p))
	return i-j;
	else
	return -1;
}

参考文献 知乎”海纳”的回答