#P18441. Karshilov's Matching Problem II
Karshilov's Matching Problem II
Karshilov's Matching Problem II
- 标准输入、标准输出;单组数据。
题目描述
Karshilov 一如既往地喜欢字符串匹配。这次,他给定一个长度为 的字符串 ,并为它的每个非空前缀赋予一个权值。具体地,长度为 的前缀记作 ,权值为 ,其中 。
对于任意字符串 ,定义
$$f(t)=\sum_{i=1}^{n} w_i\cdot\mathrm{occur}(t,\mathrm{pre}_i),$$其中 表示字符串 在 中出现的次数,允许重叠出现。例如,,。
现在,Karshilov 还有一个长度同样为 的字符串 。他将给出 个询问,每个询问包含两个整数 ,要求计算 。其中 是从第 个字符到第 个字符的子串,下标从 开始,两端均包含。
你能像两年前那样解决这些询问吗?
输入格式
第一行包含两个整数 (),分别表示两个字符串的长度和询问数。
第二行是长度为 的字符串 。
第三行是长度为 的字符串 。
第四行包含 个整数 (),表示 的各个前缀的权值。
接下来 行,每行两个整数 (),表示一次询问。
均只含小写英文字母。询问可以重复。答案不取模。
输出格式
输出 行。第 行输出一个整数,表示第 个询问的答案。
原样例 1
输入:
8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8
输出:
1
3
3
16
38
原样例 2
输入:
15 4
heheheheehhejie
heheheheheheheh
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
2 3
4 8
2 6
1 15
输出:
3
13
13
174