引入
给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l, r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。
现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
定义一个字符串 \(s\) 的 border 为 \(s\) 的一个非 \(s\) 本身的子串 \(t\)，满足 \(t\) 既是 \(s\) 的前缀，又是 \(s\) 的后缀。
对于 \(s_2\)，你还需要求出对于其每个前缀 \(s'\) 的最长 border \(t'\) 的长度。
思路
1.计算答案
容易想到暴力做法，从第一位开始枚举，如果包含则 \(ans+1\)，接着从第二位开始，以此类推……时间复杂度为 \(O(nm)\)。
我们观察哪里可以优化，可以发现第二层的 \(m\) 是无法优化的，只能优化外层的 \(n\)。其实没有必要从 \(1\) 枚举到 \(n\)，不然会有重复比较的部分，比如：(这张图好像画错了，懒得画了，是这个意思就行)
所以 \(Knuth\) 发明了一个 \(fail\) 表(失败回退表)。\(fail_i\) 定义为最长的前缀后缀相等长度值(即题面的 border)，如下图计算：
有了这个失败回退表，那么就很好做了，依次匹配，如果有不符合的就回退就好了：
Tips:
1.回退表是 \(b\) 字符串的。
2.\(j\) 表示的是已匹配的长度，而不是当前匹配的是哪一位
for(int i=1;i<=n;i++){while(j&&b[j+1]!=a[i]) j=fail[j];//回退if(b[j+1]==a[i]) j++;if(j==m){//如果包含cout<<i-m+1<<"\n";j=fail[j];}
}
2.计算 fail 表
那么我们如何计算这个 fail 表，容易发现 fail 表除了 0 以外，其他的数字一定是连续递增的。
所以我们初始化 \(fail_1 = 0\)，用类似于计算答案的方法计算 \(fail\) 表。
fail[1]=0;
for(int i=2;i<=m;i++){while(j&&b[j+1]!=b[i]) j=fail[j];//匹配不了就回退if(b[j+1]==b[i]) j++;//是否匹配fail[i]=j;
}
两者合起来就是 KMP 算法了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int N=1e6+5;
char a[N],b[N];
int fail[N],n,m;
signed main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>(a+1);cin>>(b+1);n=strlen(a+1),m=strlen(b+1);int j=0;fail[1]=0;for(int i=2;i<=m;i++){while(j&&b[j+1]!=b[i]) j=fail[j];if(b[j+1]==b[i]) j++;fail[i]=j;}j=0;for(int i=1;i<=n;i++){while(j&&b[j+1]!=a[i]) j=fail[j];if(b[j+1]==a[i]) j++;if(j==m){cout<<i-m+1<<"\n";j=fail[j];}}for(int i=1;i<=m;i++){cout<<fail[i]<<" ";}return 0;
}