匹配统计(KMP)

goto

用 KMP 先求出以 a[i] 为结尾的前缀与 b 匹配的最长长度.

比如 f[i]=j，就表示 a[1i] 的后缀最多可以和 b[1j] 匹配.但求出这个并不意味着以 a[i-j+1] 为开头的后缀可以和 b 恰好匹配 j 位（因为也许后面还可以匹配），但是可以肯定的是他至少可以匹配 j 位.我们很难求出恰好可以匹配 x 位的位置有多少，但是我们可以存至少可以匹配 x 位的位置的数目，结果用 cnt[x]-cnt[x +1] 就可以了.

因此 cnt[f[i]] ++ 就很显然了.

由于我们之前求出的是最长长度，因此当 a[1i] 可以最多和 b[1j] 匹配时，也一定存在一个小于 j 的 k 使得 a[1i] 和 b[1k] 匹配，也就是一定能找到一个位置，至少匹配 k 位，但这个可能我们在之前没有加上过.而这个 k 恰好就等于 next[j].

代码

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

int m,n,q,Next[200005],f[200005],F[200005];
char a[200005],b[200005];

int main(){
    cin>>n>>m>>q;
    scanf("%s%s",a+1,b+1);
    for (int i=2,j=0;i<=m;++i){
        while (j!=0 && b[i]!=b[j+1]) j=Next[j];
        if (b[i]==b[j+1]) j++;
        Next[i]=j;
    }
    for (int i=1,j=0;i<=n;++i){
        while (j && a[i]!=b[j+1] || j==m) j=Next[j];
        if (a[i]==b[j+1]) j++;
        f[i]=j;
    }
    for (int i=1;i<=n;++i){
        F[f[i]]++;
    }
    for (int i=m;i>=1;--i){
        F[Next[i]]+=F[i];
    }

    for (int i=1;i<=q;++i){
        int x;
        scanf("%d",&x);
        printf("%d\n",F[x]-F[x+1]);
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/102/