关于KMP算法

Posted on 2017-10-25 00:31:19

字符串匹配

暴力匹配的效率太低,没有充分利用已匹配信息,故而有了KMP算法(话说K就是Donald Knuth)。

一个小问题

贵院的选修课数据结构讲到了KPM算法,倒是不难理解,可以看这里,也就不再多说了。
只是我对于next数组的计算方式犹有疑惑

void GetNext(char* p,int next[])  {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1) { 
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

结果是形如

i 0 1 2
p[i] a b a
next[i] -1 0 0

显然在p[2]处失配时p应当右移i+1=3而不是右移i-0=i,造成额外的无效的重复匹配。
询问钱神之后得到了这篇文章,3.3.8节Next 数组的优化正是我的小疑惑。
也就是说不应当允许p[i]=p[next[i]]这种情况出现。


虽然在小细节上花了不少时间,但搞清楚之后却是豁然开朗。
另外竟然没能把特殊情况抽象到p[i]=p[next[i]],果然还是太菜了。


哎呀一不小心程序员节过去了……
学而为码农,实在很开心:)