#71. 匹配统计

匹配统计

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

阿轩在纸上写了两个字符串,分别记为A\red{A}B\red{B}

利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串A\red{A}从任意位置开始的后缀子串”与“字符串B\red{B}”匹配的长度。

不过阿轩是一个勤学好问的同学,他向你提出了Q\red{Q}个问题:

在每个问题中,他给定你一个整数x\red{x},请你告诉他有多少个位置,满足“字符串A\red{A}从该位置开始的后缀子串”与B\red{B}匹配的长度恰好为x\red{x}

例如:A=aabcdeB=ab\red{A=aabcde,B=ab},则A\red{A}aabcdeabcdebcdecdedee\red{aabcde、abcde、bcde、cde、de、e}这6个后缀子串,它们与B=ab\red{B=ab}的匹配长度分别是120000\red{1、2、0、0、0、0}

因此A\red{A}4\red{4}个位置与B\red{B}的匹配长度恰好为0\red{0},有1\red{1}个位置的匹配长度恰好为1\red{1},有1\red{1}个位置的匹配长度恰好为2\red{2}

输入格式

第一行输入三个整数N,M,Q\red{N,M,Q},分别表示A\red{A}串长度、B\red{B}串长度、问题个数。

第二行输入字符串A\red{A},第三行输入字符串B\red{B}

接下来Q\red{Q}行每行输入1\red{1}个整数x\red{x},表示一个问题。

输出格式

输出共Q\red{Q}行,依次表示每个问题的答案。

样例

输入样例

6 2 5
aabcde
ab
0
1
2
3
4

输出样例

4
1
1
0
0

提示

1N,M,Q,x200000\red{1≤N,M,Q,x≤200000}

测试

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-11-18 18:00
结束于
2023-11-18 21:00
持续时间
3 小时
主持人
参赛人数
8