#P18441. Karshilov's Matching Problem II

Karshilov's Matching Problem II

Karshilov's Matching Problem II

  • 标准输入、标准输出;单组数据。

题目描述

Karshilov 一如既往地喜欢字符串匹配。这次,他给定一个长度为 nn 的字符串 SS,并为它的每个非空前缀赋予一个权值。具体地,长度为 ii 的前缀记作 prei\mathrm{pre}_i,权值为 wiw_i,其中 1≤i≤n1\le i\le n。

对于任意字符串 tt,定义

$$f(t)=\sum_{i=1}^{n} w_i\cdot\mathrm{occur}(t,\mathrm{pre}_i),$$

其中 occur(t,p)\mathrm{occur}(t,p) 表示字符串 pp 在 tt 中出现的次数,允许重叠出现。例如,occur(heheh,heh)=2\mathrm{occur}(\texttt{heheh},\texttt{heh})=2,occur(hhh,h)=3\mathrm{occur}(\texttt{hhh},\texttt{h})=3。

现在,Karshilov 还有一个长度同样为 nn 的字符串 TT。他将给出 mm 个询问,每个询问包含两个整数 l,rl,r,要求计算 f(T[l,r])f(T[l,r])。其中 T[l,r]=TlTl+1⋯TrT[l,r]=T_lT_{l+1}\cdots T_r 是从第 ll 个字符到第 rr 个字符的子串,下标从 11 开始,两端均包含。

你能像两年前那样解决这些询问吗?

输入格式

第一行包含两个整数 n,mn,m(1≤n,m≤1500001\le n,m\le150000),分别表示两个字符串的长度和询问数。

第二行是长度为 nn 的字符串 SS。

第三行是长度为 nn 的字符串 TT。

第四行包含 nn 个整数 w1,w2,…,wnw_1,w_2,\ldots,w_n(0≤wi≤1080\le w_i\le10^8),表示 SS 的各个前缀的权值。

接下来 mm 行,每行两个整数 l,rl,r(1≤l≤r≤n1\le l\le r\le n),表示一次询问。

S,TS,T 均只含小写英文字母。询问可以重复。答案不取模。

输出格式

输出 mm 行。第 ii 行输出一个整数,表示第 ii 个询问的答案。

原样例 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