简单复习一下KMP算法（模式匹配）

KMP算法用来做什么

KMP算法用于在线性时间内判定字符串$A[1,n]$是否为字符串$B[1,m]$的子串，并求出$A$在$B$中各次出现的位置。

关于哈希求解

关于模式匹配，我们显然可以用哈希在线性时间内求解，但是过于呆板难以扩展。

由于哈希代替各种字符串的做法比较固定，此处不做介绍。

KMP算法的小复习

$fail[i]$表示“$A$中以$i$结尾的非前缀子串”与“$A$的前缀”能够匹配的最长长度，即： $$fail[i]=max\{j\},j<i,A[i-j+1,i]=A[1,j]$$

fail[1]=0; for(int i=2,j=0;i<=n;i++) { while(j&&a[i]!=a[j+1]) j=fail[j]; if(a[i]==a[j+1]) j++;fail[i]=j; }

$f[i]$表示“$B$中以$i$结尾的子串”与“$A$的前缀”能够匹配的最大长度，即： $$f[i]=max\{j\},j\le i,B[i-j+1,i]=A[i,j]$$

for(int i=1;j=0;i<=m;i++) { while(j&&(j==n||b[i]!=a[j+1])) j=fail[j]; if(b[i]==a[j+1]) j++;f[i]=j; }

放在一起就得到最后的KMP算法：

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define db double #define sg string #define ll long long #define rel(i,x,y) for(ll i=(x);i<(y);i++) #define rep(i,x,y) for(ll i=(x);i<=(y);i++) #define red(i,x,y) for(ll i=(x);i>=(y);i--) #define res(i,x) for(ll i=head[x];i;i=nxt[i]) using namespace std; const ll N=1e6+5; const ll Inf=1e18; const db Eps=1e-10; char a[N],b[N];ll n,m,f[N],fail[N]; inline ll read() { ll x=0;char ch=getchar();bool f=0; while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?-x:x; } void kmp() { int cnt=0;fail[1]=0; for(int i=2,j=0;i<=n;i++) { while(j&&a[i]!=a[j+1]) j=fail[j]; if(a[i]==a[j+1]) j++;fail[i]=j; } for(int i=1,j=0;i<=m;i++) { while(j&&(j==n||b[i]!=a[j+1])) j=fail[j]; if(b[i]==a[j+1]) j++;f[i]=j; if(f[i]==n) { cnt++;printf("%lld\n",i+1-n); } } for(int i=1;i<=n;i++) printf("%lld ",fail[i]); } int main() { scanf("%s",b+1),m=strlen(b+1); scanf("%s",a+1),n=strlen(a+1); kmp(); return 0; }