数据结构（超详细讲解！！）第十八节 串（KMP算法）

1.BF算法

算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。

最好情况下的时间复杂度为O(m)。

最坏情况下的时间复杂度为O(n×m)。

平均的时间复杂度为O(n×m)。

2.KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。        

该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

设串s的长度为n，串t长度为m。        

在KMP算法中求next数组的时间复杂度为O(m)，在后面的匹配中因主串s的下标不减即不回溯，比较次数可记为n，所以KMP算法平均时间复杂度为O(n+m)。        

最坏的时间复杂度为O(n × m)。

int KMPIndex(SqString s,SqString t) 
{     int next[MaxSize], i=0, j=0;GetNext(t,next);while (i<s.length && j<t.length) {  if (j==-1 || s.data[i]==t.data[j]) {    i++;j++;			//i、j各增1}else   j=next[j]; 		//i不变，j后退}if (j>=t.length)return(i-t.length);		//返回匹配模式串的首字符下标elsereturn(-1);		/

由模式串t求next值的算法：

void GetNext(SString t,int next[])	 
{     int j, k;j=0;  k=-1;  next[0]=-1;while (j<t.length-1){	if (k==-1 || t.data[j]==t.data[k]){      j++; k++;next[j]=k;}else  k=next[k];}
}