字符串匹配（codevs 1404）

题目描述 Description

给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。
N，M，K<=200000

输入描述 Input Description

第一行三个数 N，M，K，表示A的长度、B的长度和询问数。
第二行为串A。
第三行为串B。
接下来K行，每行1个数X。

输出描述 Output Description

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

样例输入 Sample Input

6 2 2
aabcde
ab
0
2

样例输出 Sample Output

4
1

数据范围及提示 Data Size & Hint

各个测试点1s

/*
  num[i]表示s1数组匹配到i位置时的匹配长度
  sum[i]表示长度能匹配到i的串的个数，所以询问时要减去sum[i+1]
  sum的求法：
    首先求出num，然后sum[num[i]]++，并且i的匹配长度也是满足fail[i]的 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 200010
using namespace std;
int fail[M],num[M],s1[M],s2[M],len1,len2,m;
int sum[M];
void get_fail()
{
    fail[1]=0;
    for(int i=2;i<=len2;i++)
    {
        int p=fail[i-1];
        while(p&&s2[p+1]!=s2[i])p=fail[p];
        if(s2[p+1]==s2[i])
          fail[i]=p+1;
        else fail[i]=0;
    }
}
void kmp()
{
    int p=0;
    for(int i=1;i<=len1;i++)
    {
        while(p&&s1[i]!=s2[p+1])p=fail[p];
        if(s1[i]==s2[p+1])p++;
        num[i]=p;
        if(p==len2)p=fail[p];
    }
    for(int i=1;i<=len1;i++)sum[num[i]]++;
    for(int i=len2;i>=1;i--)sum[fail[i]]+=sum[i];
}
int main()
{
    scanf("%d%d%d",&len1,&len2,&m);
    for(int i=1;i<=len1;i++)
    {
        char c;cin>>c;
        s1[i]=c;
    }
    for(int i=1;i<=len2;i++)
    {
        char c;cin>>c;
        s2[i]=c;
    }
    get_fail();
    kmp();
    while(m--)
    {
        int x;scanf("%d",&x);
        printf("%d
",sum[x]-sum[x+1]);
    }
    return 0;
}