描述
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。
N，M，K<=200000
输入格式
第二行为串A。
第三行为串B。
接下来K行，每行1个数X。
输出格式
测试样例1
输入
6 2 2
aabcde
ab
0
2
输出
4
1
代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char a[], b[];
int next[];
int used[];
int num[];
int kmp[]; int main(int argc, char **argv)
{
int i, j;
int l1, l2, s;
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d%d\n", &l1, &l2, &s);
scanf("%s\n%s", a, b); i = , j = -;
next[] = -;
while(i < l2){
if(j == - || b[i] == b[j]){
if(b[i + ] == b[j + ]){
next[i + ] = next[j + ];
}else{
next[i + ] = j + ;
}
kmp[i + ] = j + ;
i++, j++;
}else{
j = next[j];
}
} i = , j = ;
while(i < l1){
if(j == - || a[i] == b[j]){
num[i] = j + ;
used[j + ]++;
i++, j++;
}else{
j = next[j];
}
}
for(i = l2; i >= ; i--){
used[kmp[i]] += used[i];
}
for(i = ; i < s; i++){
scanf("%d", &j);
printf("%d\n", used[j] - used[j + ]);
}
return ;
}转载代码，下面题解（也是转载的）才重要
首先，这个题如果想要求出从每个位置开始的字串的匹配长度，那么O(n^2)以内的算法应该是很难的。但是，这个题要求的并不是“每个位置的长度”，而是“具有这样长度的位置数”。因而，灵活使用KMP算法自我匹配的性质，就能够解决这个问题。
考虑下面的例子：
A串：abbabbabababbababba
B串：abbabababba应用KMP算法，很容易得到B串的自我匹配是
元素 a b b a b a b a b b a
位置 1 2 3 4 5 6 7 8 9 10 11
长度 0 0 0 1 2 1 2 1 2 3 4
这个数组记为kmp[位置] = 匹配长度。由此求得到A串的各个元素尾部的匹配长度是
a b b a b b a b a b a b b a b a b b a
1 2 3 4 5 3 4 5 6 7 8 9 10 11 5 6 7 3 4统计出各个长度的出现频数
长度 0 1 2 3 4 5 6 7 8 9 10 11
频数 0 1 1 3 3 3 2 2 1 1 1 1
这个数组记作cnt[长度] = 频数。根据KMP自我匹配数组的性质，如果以A串某个元素结尾有一个长度为11的字串可以与B串匹配的话，以该元素结尾的长度为kmp[11] = 4的字串也是可以匹配的。所以说cnt[4] += cnt[11]。也就是说，进行这样的操作
for (i = N; i >= 1; i--)
cnt[kmp[i]] += cnt[i];for i := N downto 1 do
inc( cnt[ kmp[i] ] , cnt[i] );
//转载者注，inc(i)==i++
之后，cnt[i]中保存的就应该是所有长度为i的匹配字串了。这时cnt数组的状态是长度 0 1 2 3 4 5 6 7 8 9 10 11
频数 19 8 7 4 4 3 2 2 1 1 1 1然而题中要求的是“长度恰好为i”的子串的个数，也就是这些字串的下一个字符是不能匹配的。然而，cnt数组中存储的cnt[i]，必然包含了cnt[i + 1]及以上的情况。然而这很简单，“长度恰好为i”的字串数量就是cnt[i] - cnt[i + 1]，因为cnt[i]中可以扩展的字串必然都包含于cnt[i + 1]。