浅析 KMP

ingo_dtw · 2025-10-09 23:16:42 · 算法·理论

由于考场上被 KMP 创飞了，怕下次考 KMP 所以重拾 KMP。

前言

KMP 是由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 于 1977 年发明，KMP 以三人名字首字母命名。

原文地址：KMP_1977。

中文翻译（由 deepseek 完成）：KMP 中文。

说实话我最开始学 KMP 的时候没听懂除了我摸鱼以外就是看到 oi-wiki 上的解释太长了我懒得看。

所以为了帮助那些懒得看的同学我写了这篇文章。

其实我写完后发现还是很长。

正文

我们根据 oi-wiki 上对前缀函数进行定义：

给定一个长度为 n 的字符串 s，其前缀函数被定义为一个长度为 n 的数组 p。 其中 p_{i} 的定义是：

• 如果子串 s_{0\dots i} 有一对相等的真前缀与真后缀：s_{0\dots k-1} 和 s_{i - (k - 1) \dots i}，那么 p_{i} 就是这个相等的真前缀（或者真后缀，因为它们相等）的长度，也就是 p_{i}=k；
• 如果不止有一对相等的，那么 p_{i} 就是其中最长的那一对的长度；
• 如果没有相等的，那么 p_{i}=0。

然后我们来看看模板题，我们先定义 siz_1 为 s_1 的长度 siz_2 为 s_2 的长度，我们由题面可知题目让我们求出 s_2 在 s_1 出现的位置，于是我们观察下题面和刚才对于 p 的定义，聪敏的你来想一想这两者有什么关联？

我们定义字符串 b=s_2+s_1（可以加一个分隔符保证不误判当然不能是 s_2 或者 s_1 里的字符）对于 b 求一下它的前缀函数我们发现对于所有的 p_i 如果 p_i=siz_2 就说明 s_2 一定在 s_1 出现过，所以答案就是 i-siz_2+1。

现在你已经知道了怎么 \mathcal{O}(n) 求 s_2 出现在 s_1 的哪，接下来我们来看看前缀函数怎么求。

众所周知我们暴力求一个字符串 s 的前缀函数是 \mathcal{O}(n^3) 的。

for(int i=1;i<=n;i++)
{
    for(int j=i;j;j--)
    {
        if(s.substr(0,j)==s.substr(i-j+1,i))
        {
            p[i]=j;
            break;
        }
    }
}

但是我们仔细观察一下代码发现，p_i\le i 然后 p_{i+1}-p_i\ge 1 所以你会发现 p_{i+1} 每次最多增加 1 所以我们可以把第二个循环的 j 的初始值设为 p_{i-1}+1 所以时间复杂度来到 \mathcal{O}(n^2)。

但是 \mathcal{O}(n^2) 的时间复杂度还是会 T 飞，我们发现我们每次处理完一个 p_i，我们又要去枚举一个 j 来确认是否相等，于是这个时候 KMP 三人想到可不可以用已知信息来保证不重复枚举？事实上是可以的，我们发现如果 s_{i+1}=s_{p_i}（因为下标从 0 开始）那么 p_{i+1} 最好的取值一定是 p_i+1 但是如果不相等呢？那我们最优的不行次优的呢？于是我们考虑一直往前面找直到 s_{i+1}=s_{p_i} 如果 i 都为 0 了还是没找到那 p_{i+1} 就为 0。

但是我学到这里想到为什么 while(j>0&&a[i]!=a[j+1]) j=nxt[j]; 其中 j=nxt[j] 为什么 nxt_j 一定是次优的？我们画个图你就知道了：

S: [前缀]...[后缀]?
    ~~~~   ~~~~  ^
     j个    j个   i

现在如果不匹配，我要找一个 s_{1\dots j} 里稍微小一点的前缀使得与 s_{i-j\dots i-1} 的一段后缀匹配，那么也就是长度为 j 的最长公共前后缀，所以不匹配时 j 最好回退到 nxt_j。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif   
#define int long long
#define ull unsigned long long
#define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char x)
{
return !(x^9)||!(x^13)||!(x^10)||!(x^32);
}
template<class T>inline T read()
{
    T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(int x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());   
}
const int N=1e6+10;
int nxt[N],f[N];
signed main()
{
    string a,b;
    cin>>b>>a;
    rint n=b.size(),m=a.size();
    a=' '+a,b=' '+b;
    nxt[1]=0;
    for(rint i=2,j=0;i<=m;i++) 
    {
        while(j>0&&a[i]!=a[j+1]) j=nxt[j];
        if(a[i]==a[j+1]) j++;
        nxt[i]=j;
    }
    for(rint i=1,j=0;i<=n;i++) 
    {
        while(j>0&&(j==n||b[i]!=a[j+1])) j=nxt[j];
        if(b[i]==a[j+1]) j++;
        f[i]=j;
        if(f[i]==m) 
        {
            out(i-m+1);
            pc('\n');
        }
    }
    for(rint i=1;i<=m;i++)
    {
        out(nxt[i]);
        pc(' ');
    }
    return 0;
}

:::

我们来分析下时间复杂度： 观察代码中的 while 循环：虽然看起来可能很慢，但实际上 j 指针的移动是有规律的：

• 因此总的操作次数是 \mathcal{O}(n) 的。

拓展

最小循环元

一般来说，KMP 还可以解决最小循环元的问题，我们先说结论，对于长度为 i 的字符串我们对它进行 KMP 自我匹配那么它的最小循环元长度为 i-nxt_i，循环次数为 i\div (i-nxt_i)，为什么是这样呢，我们设 S 为字符串 P 循环 k 次构成，那么：