← 返回题目列表

Codeforces · 1313/E

E. 与交集串联

中文机器翻译题面 查看原题

Vasya 有三个字符串 $$$a$$$、$$$b$$$ 和 $$$s$$$,由小写英文字母组成。字符串$$$a$$$和$$$b$$$的长度等于$$$n$$$,字符串$$$s$$$的长度等于$$$m$$$。

Vasya 决定选择字符串 $$$a$$$ 的子字符串,然后选择字符串 $$$b$$$ 的子字符串并将它们连接起来。形式上,他选择一个段 $$$[l_1, r_1]$$$ ($$$1 \leq l_1 \leq r_1 \leq n$$$) 和一个段 $$$[l_2, r_2]$$$ ($$$1 \leq l_2 \leq r_2 \leq n$$$),连接后他得到一个字符串 $$$a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}$$$。

现在,Vasya 感兴趣的是计算选择符合以下条件的细分的方法数量:

- 线段 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 有非空交集,即存在至少一个整数 $$$x$$$,使得 $$$l_1 \leq x \leq r_1$$$ 和 $$$l_2 \leq x \leq r_2$$$;
- 字符串 $$$a[l_1, r_1] + b[l_2, r_2]$$$ 等于字符串 $$$s$$$。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n$$$) - 字符串 $$$a$$$ 和 $$$b$$$ 的长度以及字符串 $$$s$$$ 的长度。

接下来的三行分别包含字符串 $$$a$$$、$$$b$$$ 和 $$$s$$$。字符串$$$a$$$和$$$b$$$的长度是$$$n$$$,而字符串$$$s$$$的长度是$$$m$$$。

所有字符串均由小写英文字母组成。

输出

打印一个整数 — 选择满足 Vasya 条件的一对线段的方法数。

示例

输入 #1

6 5
aabbaa
baaaab
aaaaa

输出 #1

4

输入 #2

5 4
azaza
zazaz
azaz

输出 #2

11

输入 #3

9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz

输出 #3

2

注意

让我们列出 Vasya 在第一个示例中可以选择的所有线段对:

1. $$$[2, 2]$$$ 和 $$$[2, 5]$$$;
2. $$$[1, 2]$$$ 和 $$$[2, 4]$$$;
3. $$$[5, 5]$$$ 和 $$$[2, 5]$$$;
4. $$$[5, 6]$$$ 和 $$$[3, 5]$$$;