问题 P: 匹配统计
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:6
解决:4
题目描述
阿轩在纸上写了两个字符串,分别记为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。
不过阿轩是一个勤学好问的同学,他向你提出了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
第二行是字符串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