题目描述

给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。

给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。

N，M，K<=200000

输入

第一行三个数 N，M，K，表示A的长度、B的长度和询问数。

第二行为串A。

第三行为串B。

接下来K行，每行1个数X。

输出

对于每个询问输出一个数。

样例输入

6 2 2

aabcde

ab

0

2

样例输出

4

1

---

题解

KMP先求出next数组，匹配一遍，统计一下某长度出现的次数num。

这是以每个字符结尾的出现次数，然而落下了一部分。

为了得到总数，需要从后向前执行num[next[i]]+=num[i]可以得到能够匹配某长度的个数。

而题目要求是“恰好匹配”，所以答案为num[i]-num[i+1]。

KMP细节太多了。。。

#include 
       
        #include 
        
         char A[200001] , B[200001];int next[200001] , num[200001];int main(){    int n , m , k , i , j;    scanf("%d%d%d%s%s" , &n , &m , &k , A , B);    for(i = 1 ; i < m ; i ++ )    {        j = next[i];        while(j && B[i] != B[j]) j = next[j];        if(B[i] == B[j]) next[i + 1] = j + 1;        else next[i + 1] = 0;    }    for(i = j = 0 ; i < n ; i ++ )    {        while(j && A[i] != B[j]) j = next[j];        if(A[i] == B[j]) j ++ ;        num[j] ++ ;    }    for(i = m ; i > 0 ; i -- )        num[next[i]] += num[i];    while(k -- )    {        scanf("%d" , &i);        printf("%d\n" , num[i] - num[i + 1]);    }    return 0;}