KMP算法

Author Avatar
洛水·锦依卫 1月 25, 2019

KMP-字符串匹配算法

思想

正常枚举以每个字符为起点的$|S| × |T|$的朴素算法效率太过低下,对于已经匹配过的位置,我们应该节省这段时间。那么就需要$KMP$的失配数组。我们记录$f[i]$为前$i$个字符最长的前缀后缀相同的连续串长度,当此处已经匹配至位置$i$,那么不应该浪费这一段匹配的距离,我们可以把前面相同的串拉过来继续匹配。当然刻意卡的话还是$n × m$的。。。

代码

失配转移数组

for(int i=1;i<len;i++)
{
    int j=f[i];
    while(j&&P[j]!=P[i])
        j=f[j];
    f[i]=P[i]==P[j]?j+1:0;
}

匹配过程

int j=0;
for(int i=0;i<LEN;i++)
{
    while(j&&P[j]!=T[i])
        j=f[j];
    if(P[j]==T[i])
        j++;
    if(j==m)
        cout<<i-m+1<<endl;
}