今天复习到数据结构中的串的模式匹配了，发现以前上课听课的东西现在已经忘得一干二净了，经过半个小时研究，我终于有会了。
KMP算法用于串的模式匹配，废话不多说，写一个串。
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 模式串 | a | b | a | a | b | c | a | c |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 |
next 函数定义
- j=1
第一位 next[j] 为0 - j=2
第二位 next[j] 为1
其他值都是在这两个值的基础之上计算的。 - j=3
第三位 next[j]为：第二位字符是“b”，其 next[j] 值为1，则判断 “b”是否和第一位字符“a”相等，显然不等对吧，所以其值为1。（凡是其他不相等的情况 next[j] 的值都为1） - j=4
第四位 next[j]为：第三位字串是“a”，其 next[j] 值为1,判断“a”是否和第一位字符“a”相等，相等则 1+1=2 - j=5
第五位 next[j]为：第四位字符是“a”，其 next[j] 值为2,判断“a”是否和第二位字符“b”相等，不相等，则把第二位字符的 next[j] 相对应的字符和第四位字符做比较，即判断“a”是否和第一位字符“a”相等，相等则 1+1=2 - j=6
第六位 next[j]为：第五位字符是“b”，其 next[j] 值为2,判断“a”是否和第二位字符“b”相等，相等则 2+1=3 - j=7
第七位 next[j]为：第六位字符是“c”，其 next[j] 值为3,判断“c”是否和第三位字符“a”相等，不相等，则把第三位字符的 next[j] 相对应的字符和第七位字符做比较，则判断“c”是否和第一位字符“a”相等，不相等则值为 1 - j=8
第八位 next[j]为：第七位字串是“a”，其 next[j] 值为1,判断“a”是否和第一位字符“a”相等，相等则 1+1=2
相信大家看完我上面罗列的计算过程，都应该学会了把，那么就可以将上面的算法实现一下：
void get_next(SString T,int next[])
{//求模式串 T 的 next 函数值并存入数组 next 中
int i=1;int j=0;
next[1]=0;
while(j<T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
这个算法的复杂度为O(n+m)。这个算法已经够完美了，但是也有美中不足的地方，看下面的例子：
| j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 模式串 | a | a | a | a | a | b |
| next[j] | 0 | 1 | 2 | 3 | 4 | 5 |
在这个例子中，第1~5个字符都相等，都是“a”，但是匹配的时候还是要重新做比较，其实完全可以省去那些没有必要的比较，于是算法有了最新的该进。
| j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 模式串 | a | a | a | a | a | b |
| next[j] | 0 | 1 | 2 | 3 | 4 | 5 |
| nextval[j] | 0 | 0 | 0 | 0 | 0 | 5 |
void get_next(SString T,int nextval [])
{//求模式串 T 的 next 函数修正值值并存入数组 nextval 中
int i=1;int j=0;
nextval [1]=0;
while(j<T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
if(T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=j;
}
else
j=nextval[j];
}
}
