【CH1809】匹配统计（KMP）

题目链接

摘自https://www.cnblogs.com/wyboooo/p/9829517.html

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

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

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

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

xjc大佬还提出了一个hash+二分的做法，也能AC。

就是用二分长度+hash check求出每个位置的答案，然后直接用桶记录秒出答案。

时间复杂度\(O(n\log n)\)

#include <cstdio>

#include <cstring>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

const int MAXN = 200010;

int nxt[MAXN], n, m, q, f[MAXN], c[MAXN], d;

char a[MAXN], b[MAXN];

int main(){

    Open("str");

    scanf("%d%d%d%s%s", &n, &m, &q, a + 1, b + 1);

    int j = 0;

    for(int i = 2; i <= m; ++i){

        while(j && b[i] != b[j + 1]) j = nxt[j];

        if(b[j + 1] == b[i]) ++j;

        nxt[i] = j;

    }

    j = 0;

    for(int i = 1; i <= n; ++i){

        while(j && (a[i] != b[j + 1] || j == m)) j = nxt[j];

        if(a[i] == b[j + 1]) ++j;

        f[i] = j;

    }

    for(int i = 1; i <= n; ++i)

        ++c[f[i]];

    for(int i = m; i; --i)

    	c[nxt[i]] += c[i];

    for(int i = 1; i <= q; ++i){

        scanf("%d", &d);

        printf("%d\n", c[d] - c[d + 1]);

    }

    return 0;

}

巴特西

【CH1809】匹配统计（KMP）

最新文章

热门文章