KMP 算法

字符串匹配问题

给定字符串 $s_1$ ，以及模式串 $s_2$ ，求 $s_2$ 在 $s_1$ 内的所有出现位置。

一个很朴素的想法就是一位一位进行比较，复杂度 $O(MN)$ ， $M,N$ 为两字符串长度。

const int N = 1e6+5;
char s1[N],s2[N];
void brute_force(){
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(int i=0;i+l2<=l1;i++){
        bool flag=1;
        for(int j=0;j<l2;j++){
            if(s1[i+j]!=s2[j]){
                flag=0;break;
            }
        }
        if(flag)printf("match at %d\n",i);
    }
}

KMP 算法

然而，KMP 算法可以让我们在 $O(M+N)$ 的时间复杂度内求出所有出现位置。（算法名字来源于三个发明者的姓名首字母）

其核心思想就是减少不必要的比较操作（一位一位跳太慢了，有时候我们可以比较了之后就一次跳好多位）

next 数组

next 数组代表一个下标失配后，可以直接跳过多少个字符。

next[i] 的定义为，模式串 $s_2$ 的前缀 $[1\ldots i]$ 中，相同的真前缀和真后缀最大长度。

来看一个例子：

那么这个 next 数组到底怎么用呢？

我们用两个指针 i，j，分别代表目前在查找的字符串和模式串里面的匹配位置。考虑现在匹配到 ABABA，最后一位的 A 失配。

接下来发生了什么事情呢？

i 的位置保持不变
j 的位置跳转到最后一位匹配的对应 next 值后一个位置（2+1=3）

这是什么意思呢？其实 ABAB 的最长相同的真前缀和真后缀长度是 2，即 AB 和 AB，这就代表我们现在匹配成功的 ABAB，其实最后两个字符已经是匹配好的下一个的开头了（而且最长就是 2，所以说一定是用重复的 AB）。所以我们已经匹配好了最后的两个 AB，而 j 的位置就跳到了匹配完 AB 的下一个，继续进行匹配。

再看一个例子：

如果第一个字符就失配了，我们直接将 i 后移一位。

综上我们可以写出代码。

void kmp(){
    // j表示当前匹配了几个字符
    // s为搜索串, t为模式串，长度分别为n,m
    for(int i=1,j=0;i<=n;i++){
        while(j && t[j+1]!=s[i])j=nxt[j]; // 尝试匹配下一位，但是失败了。
        if(t[j+1] == s[i])j++; // 能匹配吗
        if(j==m)cout<<i-m+1<<'\n'; // 匹配完了
    }
}

看到这里，有的小朋友就要问了：我看这里的 j 不是会往回跳吗？那万一疯狂往回跳，复杂度不就变成 $O(nm)$ 了吗？

事实上，如果仔细想一想，就能发现，j 每往回跳一次，就至少匹配一次（只有匹配的时候 j 增加了），最多匹配 $n$ 次，那么最多往回跳 $n$ 次。

因此，匹配的复杂度是 $\Theta(n)$ 的。

求解 next 数组

接下来就只需要求出 next 数组了。

考虑从前一位的 next 数组递推。由于前一位的 next 数组已经保证了 [0..nxt[i-1]],[i-nxt[i-1]...i-1] 是相同的。

s[nxt[i-1]+1] = s[i]

如图，显然 nxt[i] = nxt[i-1]+1。
s[nxt[i-1]+1] != s[i]

我们尝试退而求其次，找一个比较短的部分公共前缀部分进行匹配。而其的最长的就是紫色这里的 nxt 数值，因此我们将已经匹配的长度减小到 1，然后再看是否可以匹配。（注意，这里的找一个比较短的部分的过程可以进行多次）

void cal_next(){
    // j 为目前匹配到的公共前后缀长度
    for(int i=2,j=0;i<=m;i++){
        while(j && t[j+1]!=t[i])j=nxt[j]; // 匹配下一位 
        if(t[j+1]==t[i])j++;
        nxt[i]=j;
    }
}

如何说明复杂度？观察 j，不难发现 j 最多只会增加 $m$ 次，所以也最多只会往回跳 $m$ 次。

完整代码

[洛谷P3375] 【模板】KMP 字符串匹配

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+6;
char s[N],t[N];
int nxt[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>(s+1)>>(t+1);
    int n=strlen(s+1),m=strlen(t+1);
    
    for(int i=2,j=0;i<=m;i++){
        while(j && t[j+1]!=t[i])j=nxt[j];
        if(t[j+1]==t[i])j++;
        nxt[i]=j;
    }

    for(int i=1,j=0;i<=n;i++){
        while(j && t[j+1]!=s[i])j=nxt[j];
        if(t[j+1] == s[i])j++;
        if(j==m)cout<<i-m+1<<'\n';
    }

    for(int i=1;i<=m;i++)cout<<nxt[i]<<' ';
    cout<<'\n';

    return 0;
}