KMP算法中的next函数

今天复习到数据结构中的串的模式匹配了，发现以前上课听课的东西现在已经忘得一干二净了，经过半个小时研究，我终于有会了。

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];
    }
}