3475. [CH 1809]匹配统计

【题目描述】

阿轩在纸上写了两个字符串，分别记为 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，表示一个问题。

【输出格式】

共 q 行，依次表示每个问题的答案。

【样例输入】

6 2 5
aabcde
ab
0
1
2
3
4

【样例输出】

4
1
1
0
0

【数据范围与约定】

1 ≤ n, m, q, x ≤ 2 × 10^5。

【来源】

《算法竞赛进阶指南》