串的定义 ：串是由零个或多个字符组成的有限序列。

S= ‘a1a2…an-1an ’ (n≥0)

子串： 串中任意个连续的字符组成的子序列。

主串：包含子串的串相应地称为主串。

位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

相等：两个串的长度相等，并且对应位置的字符都相等。

 

串的抽象数据类型的定义

串的模式匹配

1. 简单匹配算法

主串S中的子串与模式串T进行比较,直 到找到相同的子串为止。 如果存在相同的子串，则匹配成功，返回子串在主串S中的位置pos。 否则匹配不成功。

子串与模式的比较策略: 从前到后依次进行比较。

  时间复杂度:O(n*m)

int Index(SString S, int pos, SString T)
{   int i = pos, j =1;while (i <= S.len && j <=T.len){if (S.ch[i] == T.ch[j]){ ++i;++j;   }else{ i = i-j+2;j = 1; }}if (j > T.len)return i - T.len;elsereturn 0; 
} 

2. KMP算法

KMP为(D.E.Knuth 与J.H.Morris和 V.R.Pratt)同时发现的算法，因此人们称之为 克努特－莫里斯－普拉特算法。

特点是在匹配的过程中，不需要回溯主 串的指针i，且时间复杂度可以达到O(m+n)

 

时间复杂度:O(n+m)

int Index_KMP(SString S, int pos, SString T){int i = pos, j =1;while (i <= S.len && j <=T.len){if (j==0 || S.ch[i] == T.ch[j] ){  //j=0 表示此前比较的是模式串首字符且不匹配应从主串++i;                            // 后继字符起从头比较++j; }elsej = next[j];}if (j > T.len)return i - T.len;elsereturn 0;
} 

next [ j ] 值的计算与实现

 

思考

KMP算法思路:

在匹配过程出现s[i]<> t[j] 时, 不需回溯i指针, 而是利用已经得到的匹配结果将模式串向右滑 动尽可能远, 再继续比较，所有可以再引入nextval[j]优化算法

nextval函数值的算法：

void Get_Nextval(SString T, int next[ ],int nextval[ ])
{int j = 2, k =0;Get_Next(T, next);nextval[1]=0;while (j <= T.len )
{k=next[j];if( T.ch[j] == T.ch[k] )nextval[j]=nextval[k];elsenextval[j]=next[j];j++;}
}