KMP

SalN · 2022-10-17 18:20:23 · 算法·理论

我们要查询 A 是不是 B 的子串

设 g_i=\max\{j\}，其中 j<i 且 A[i-j+1],...,A[i] 等同于 A[1],...,A[j]

设 f_i=\max\{j\}，其中 j\leq i 且 B[i-j+1],...,B[i] 等同于 A[1],...,A[j]

我们先想想这个寄（雾）怎么求

那么这个 g_i 是不是应该是符合可以 g_{i-1} 的项扩展得到呢（？

考虑枚举 g_{i-1} 的项去取值，有一个小 trick

假设 x 对于 g_{i-1} 符合，那么对于 y<x 的符合项 y，\max\{y\}=g_x

其实就是，border 的 border 还是 border。

标红的表示等同的部分，我们会发现要的就是 x 跟自己的匹配（

对于这个 f 怎么求（？，定义是相似的，不多做介绍

code

char a[MN], b[MN];
int n, m, g[MN], f[MN];

scanf("%s%s", b+1, a+1);
m=strlen(b+1), n=strlen(a+1), g[1]=0;
for(int i=2, j=0; i<=n; ++i) {
    while(j>0&&a[j+1]!=a[i]) j=g[j];
    j+=(a[j+1]==a[i]), g[i]=j;
}
for(int i=1, j=0; i<=m; ++i) {
    while(j>0&&(j==n||a[j+1]!=b[i])) j=g[j];
    j+=(a[j+1]==b[i]), f[i]=j;
//  if(f[i]==n) printf("%d\n", i-n+1);
}