给出两个字符串({a_i},{b_i}),长度分别为(n,m),有q个询问，每次询问长度恰好为x的a串中的位置数量，保证以该位置为开头的前缀与({b_i})匹配长度恰好为(x,1≤n,m,q,x≤200000)。
解
匹配问题，考虑kmp,不妨利用kmp，求出串a的f数组，求出串b的next数组，接下来是玄学操作，我也不能体现思维过程了。
首先记一个(cnt[i])表示长度为至少i的满足题意的位置个数，只要求出这个每次询问x，我们只要回答(cnt[x]-cnt[x+1])，自然想到给每个i,都来一次(++cnt[f[i]])，但是这样是有问题的。
首先要了解匹配的性质，不然是无法理解的，也就是(f_i)，能够有值的部分（也就是不为０）必然是连续的一段一段，而且根据kmp性质3，对于位置j，容易知道其实(a[j+i+1sim j])能够与(b[1sim i])相同的前提为(a[j+i+1sim j-1])和(b[1sim i-1])相同，然后在判断(b[i])与(a[j])是否相同。
如果真正理解了上面的这句话（不晓得我在说什么，为什么要说这些东西，多看几遍，多画图），容易知道我们每次(++cnt[f[i]])（我们是要求一个以某个位置开头的前缀），那么必然对于一个位置开始的前缀，它的最大长度一直到0都会被统计一次，这样恰好符合了我们的(cnt[i])的含义，而显然这样是算少了，原因在于(f[i])的含义为a串以i结尾的后缀，能与b串匹配的最大长度，所以实际上对于a串在(i-f[i]+1)中的位置，还可以存在位置让其以它为开头其后缀与b串匹配。
根据kmp性质1，容易知道对于每个(f[i])，这些位置的匹配长度恰好为为(next[f[i]])，于是我们就只要倒序枚举i表示至少大于等于长度i所求的数量,每次有操作(cnt[next[i]]+=cnt[i])，而这个递推方程无后效性的原因在于(next[i])必然小于(i)，含义也就是对于长度大于等于i的位置数，其会对长度(next[i])有贡献，其实很好理解，因为长度为i肯定kmp的次优决策点就是(next[i])，而大于i的长度为j，kmp性质告诉我们j又是在i的基础上，必然满足其次优决策点为(next[j],next[next[j]]...)下去必然会等于i，而显然(cnt[i])有会包括这些情况，而无论如何这些情况都是大于(next[i])，而等于(next[i])的部分已经在之前被计算过了(++)的时候已经被计算过了。
这道题目很抽象，感性理解的部分比较多，最后时间复杂度可以做到(O(n))，代码很简单。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define Size 200500
using namespace std;
char a[Size],b[Size];
int Next[Size],f[Size],cnt[Size];
il void get(char&),
kmp(char[],int,char[],int);
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i(1);i<=n;++i)get(a[i]);
for(int i(1);i<=m;++i)get(b[i]);
kmp(b,m,a,n);for(int i(1);i<=n;++i)++cnt[f[i]];
for(int i(m);i;--i)cnt[Next[i]]+=cnt[i];
while(q--)scanf("%d",&n),printf("%d
",cnt[n]-cnt[n+1]);
return 0;
}
il void kmp(char a[],int la,char b[],int lb){
for(int i(2),j(0);i<=la;++i){
while(j&&a[j+1]!=a[i])j=Next[j];
if(a[j+1]==a[i])++j;Next[i]=j;
}for(int i(1),j(0);i<=lb;++i){
while(j&&(a[j+1]!=b[i]||j==la))j=Next[j];
if(a[j+1]==b[i])++j;f[i]=j;
}
}
il void get(char &c){
while(c=getchar(),c==' '||c=='
'||c=='
');
}