OpenJudge

6:匹配统计(填空)

总时间限制:
1000ms
内存限制:
262144kB
描述

阿轩在纸上写了两个字符串,分别记为A和B。利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串A从任意位置开始的后缀子串”与“字符串B”匹配的长度。
不过阿轩是一个勤学好问的同学,他向你提出了Q个问题:在每个问题中,他给定你一个整数x,请你告诉他有多少个位置,满足“字符串A从该位置开始的后缀子串”与B匹配的长度恰好为x。
例如:A=aabcde,B=ab,则A有aabcde、abcde、bcde、cde、de、e这6个后缀子串,它们与B=ab的匹配长度分别是1、2、0、0、0、0。因此A有4个位置与B的匹配长度恰好为0,有1个位置的匹配长度恰好为1,有1个位置的匹配长度恰好为2。

输入
第一行三个整数N,M,Q,表示A串长度、B串长度、问题个数。
第二行是字符串A,第三行是字符串B。
接下来Q行每行1个整数x,表示一个问题。
1<=N,M,Q,x<=200000.
输出
共Q行,依次表示每个问题的答案。
样例输入
6 2 5
aabcde
ab
0
1
2
3
4
样例输出
4
1
1
0
0

这是一道代码填空题,你可以填写下面代码中的空白部分后复制提交。
当然,你也可以按照你的逻辑修改非空白部分的代码,或者无视这里的代码,直接自己编写程序解答此题。
#include
#include
#include
#include
using namespace std;
const int SIZE = 200010;
int f[SIZE], next[SIZE], cnt[SIZE];
char a[SIZE], b[SIZE];
int n, m, q;

int main()
{
    cin >> n >> m >> q;
    scanf("%s", a + 1); // A[1..n]保存A串
    scanf("%s", b + 1); // B[1..m]保存B串

    for (int i = 2, j = 0; i <= m; i++) // 对B串自匹配,求next数组
    {
        ____________________(1)_____________________;
        if (b[j + 1] == b[i]) j++;
        ________(2)________;
    }

    for (int i = 1, j = 0; i <= n; i++) // A串与B串进行模式匹配
    {
        while (j>0 && (j == m || a[i] != b[j + 1])) ____(3)____;
        ____________(4)___________;
        f[i] = j;
    }

    for (int i = 1; i <= n; i++) cnt[f[i]]++;
    for (int i = m; i; i--) _____(5)_____ += cnt[i];

    // 此时cnt[x]保存的是匹配长度>=x的位置个数

    for (int i = 1; i <= q; i++)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", ________(6)________);
    }
}

注意:这是练习题,不是作业题

全局题号
9203
添加于
2017-09-06
提交次数
8
尝试人数
2
通过人数
2