KMP算法中next数组的构建

记得初学$kmp$的时候老师让大家把它直接背下来

然而不理解的话不仅调试起来比较慢很多题目也难往$kmp$上想

-----------------------------------------------------------------------

设字符串为$s$ 长度为$len$ 起始位置为$1$

首先要明白的就是 next数组的意思便是$s[$从 $1$ 到$ i]$的后缀与$s[$从 $1$到 $i -1]$的前缀的最长公共部分长度

$($假设为$k$，则$s[$从$ 1$ 到$ i]$与$s[$从$i - k$ 到 $i - 1]$匹配$)$

此处可参见NOI2014动物园的题目描述$($只用看题目描述里对$next$数组的解释便可题目无需思考$)$

于是我们便可以开始构建$next$数组了

#include <bits/stdc++.h>

using namespace std;

const int N = ;

char s[N];

int next[N];

int len;

int main()

{

    scanf("%s",s + );

    len = strlen(s + );

    next[] = ;

    int j = ;

    for(int i = ;i <= len; ++i)

    {

        while(j && s[i] != s[j + ])j = next[j];

        //不断向前寻找 直到s[从1到i]的后缀与s[从1到j+1]匹配

        //之所以j=next[j]的原因是s[从1到j]的后缀与s[从1到next[j]]匹配

        //不同的只是s[j+1]与s[next[j]+1] 这一点也可以解释为何只需最后一位匹配

        if(s[i] == s[j + ])

            next[i] = ++j;

        //若匹配成功 则最长公共部分长度为n+1

        else

            next[i] = ;

        //否则 无公共部分

    }

    for(int i = ;i <= len; ++i)

        printf("%d ", next[i]);

}

自认为字符串下标从$1$开始比从$0$开始使人更易理解$next$数组的含义$($然而大部分$kmp$模板中字符串下标都是从$0$开始的$)$

秒客网

KMP算法中next数组的构建

相关文章