描述
给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。
N，M，K<=200000
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。
N，M，K<=200000
输入格式
第一行三个数 N，M，K，表示A的长度、B的长度和询问数。
第二行为串A。
第三行为串B。
接下来K行，每行1个数X。
第二行为串A。
第三行为串B。
接下来K行，每行1个数X。
输出格式
对于每个询问输出一个数。
测试样例1
输入
6 2 2
aabcde
ab
0
2
输出
4
1
题解
kmp的应用。不得不说我字符串的处理没好好学。
这位神犇的解释很清楚：http://www.cnblogs.com/neverforget/archive/2012/03/27/2419621.html
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,k,nx[200005],l[200005],ans[200005];
char a[200005],b[200005];
void init()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a+1,b+1);
/*int i; char t;
for(i=1;i<=(n+1)/2;i++) {t=a[i]; a[i]=a[n-i+1]; a[n-i+1]=t;}
for(i=1;i<=(m+1)/2;i++) {t=b[i]; b[i]=b[m-i+1]; a[m-i+1]=t;}*/
}
void pre()
{
int i,j;
nx[1]=0; j=0;
for(i=2;i<=m;i++)
{while(j>0&&b[j+1]!=b[i]) j=nx[j];
if(b[j+1]==b[i]) j++;
nx[i]=j;
}
}
void kmp()
{
int i,j=0,ct;
for(i=1;i<=n;i++)
{while(j>0&&b[j+1]!=a[i]) j=nx[j];
if(b[j+1]==a[i]) j++;
l[i]=j;
if(j==m) j=nx[j];
}
for(i=1;i<=n;i++) ans[l[i]]++;
for(i=m;i>0;i--) ans[nx[i]]+=ans[i];
}
int main()
{
init(); pre(); kmp();
while(k--)
{int x;
scanf("%d",&x);
printf("%d\n",ans[x]-ans[x+1]);
}
return 0;
}