【Tyvj1068】STR

2014-05-09
竞赛题解 / 字符串
KMPTYVJ

描述 Description

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

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

N，M，K<=200000

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

6 2 2
aabcde
ab
0
2

样例输出 SampleOutput

4
1

Tyvj 1068

代码 Code

KMP 自我匹配性质的灵活使用。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[202711],b[202711];
int pre[202711],mat[202711];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    memset(mat,0,sizeof(0));
    scanf("%d%d%dn",&n,&m,&k);
    a[0]='#';b[0]='#';
    for (i=1;i<=n;i++) scanf("%c",&a[i]);
    scanf("n");
    for (i=1;i<=m;i++) scanf("%c",&b[i]);
    pre[1]=0;
    j=0;
    for (i=2;i<=m;i++)
    {
        while (j>0 && b[j+1]!=b[i]) j=pre[j];
        if (b[j+1]==b[i]) j++;
        pre[i]=j;
    }
    j=0;
    for (i=1;i<=n;i++)
    {
        while (j>0 && b[j+1]!=a[i]) j=pre[j];
        if (b[j+1]==a[i]) j++;
        mat[j]++;
        if (j==m) j=pre[j];
    }
    for (i=n;i>=1;i--) mat[pre[i]]+=mat[i];
    for (i=1;i<=k;i++)
    {
        scanf("%d",&x);
        printf("%d\n",mat[x]-mat[x+1]);
    }
    return 0;
}