Concatenation with intersection

题意翻译

### 题目描述 给定三个串 $a,b,s$，其中 $a,b$ 长度为 $n$，$s$ 长度为 $m$，求出四元组 $(l1,r1,l2,r2)$ 的个数，满足： 1. $[l1,r1]$ 和 $[l2,r2]$ 的交集非空。 2. $a$ 中位置 $l1$ 到 $r1$ 组成的子串与 $b$ 中位置 $l2$ 到 $r2$ 组成的子串拼起来恰好是 $s$。 $1 \leq n \leq 500000$，$2 \leq m \leq 2n$。 ### 输入格式 第一行两个整数 $n,m$。 第二行一个字符串 $a$。 第三行一个字符串 $b$。 第四行一个字符串 $s$。 ### 输出格式 输出一个整数表示四元组的个数。

题目描述

Vasya had three strings $ a $ , $ b $ and $ s $ , which consist of lowercase English letters. The lengths of strings $ a $ and $ b $ are equal to $ n $ , the length of the string $ s $ is equal to $ m $ . Vasya decided to choose a substring of the string $ a $ , then choose a substring of the string $ b $ and concatenate them. Formally, he chooses a segment $ [l_1, r_1] $ ( $ 1 \leq l_1 \leq r_1 \leq n $ ) and a segment $ [l_2, r_2] $ ( $ 1 \leq l_2 \leq r_2 \leq n $ ), and after concatenation he obtains a string $ 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} $ . Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions: - segments $ [l_1, r_1] $ and $ [l_2, r_2] $ have non-empty intersection, i.e. there exists at least one integer $ x $ , such that $ l_1 \leq x \leq r_1 $ and $ l_2 \leq x \leq r_2 $ ; - the string $ a[l_1, r_1] + b[l_2, r_2] $ is equal to the string $ s $ .

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ ( $ 1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n $ ) — the length of strings $ a $ and $ b $ and the length of the string $ s $ . The next three lines contain strings $ a $ , $ b $ and $ s $ , respectively. The length of the strings $ a $ and $ b $ is $ n $ , while the length of the string $ s $ is $ m $ . All strings consist of lowercase English letters.

输出格式

Print one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.

输入输出样例

输入样例 #1

6 5
aabbaa
baaaab
aaaaa

输出样例 #1

4

输入样例 #2

5 4
azaza
zazaz
azaz

输出样例 #2

11

输入样例 #3

9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz

输出样例 #3

2

说明

Let's list all the pairs of segments that Vasya could choose in the first example: 1. $ [2, 2] $ and $ [2, 5] $ ; 2. $ [1, 2] $ and $ [2, 4] $ ; 3. $ [5, 5] $ and $ [2, 5] $ ; 4. $ [5, 6] $ and $ [3, 5] $ ;