后缀匹配计数问题

题目描述

阿轩在纸上写了两个字符串，分别记为 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 行，依次表示每个问题的答案。

输入输出样例 #1

输入样例

6 2 5
aabcde
ab
0
1
2
3
4

输出样例

4
1
1
0
0

限制条件

• $1 \le N, M, Q, x \le 200000$

时间限制

2秒

空间限制

256MB

样例解释

字符串 A = "aabcde" (长度 6) 字符串 B = "ab" (长度 2)

A 的 6 个后缀子串及其与 B 的匹配长度：

1. 从位置 1 开始：aabcde，与 B="ab" 匹配长度为 1（前缀 "a" 匹配）
2. 从位置 2 开始：abcde，与 B="ab" 匹配长度为 2（前缀 "ab" 匹配）
3. 从位置 3 开始：bcde，与 B="ab" 匹配长度为 0（前缀 "b" 不匹配 "a"）
4. 从位置 4 开始：cde，与 B="ab" 匹配长度为 0
5. 从位置 5 开始：de，与 B="ab" 匹配长度为 0
6. 从位置 6 开始：e，与 B="ab" 匹配长度为 0

统计：

• 匹配长度为 0 的位置有：3,4,5,6 → 4个
• 匹配长度为 1 的位置有：1 → 1个
• 匹配长度为 2 的位置有：2 → 1个
• 匹配长度为 3 的位置有：0个
• 匹配长度为 4 的位置有：0个

因此输出：

4
1
1
0
0