Codeforces Round 622 (Div. 2) |
---|
Finished |
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 [l1,r1] (1≤l1≤r1≤n) and a segment [l2,r2] (1≤l2≤r2≤n), and after concatenation he obtains a string a[l1,r1]+b[l2,r2]=al1al1+1…ar1bl2bl2+1…br2.
Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:
The first line contains integers n and m (1≤n≤500000,2≤m≤2⋅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.
6 5
aabbaa
baaaab
aaaaa
4
5 4
azaza
zazaz
azaz
11
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz
2
Let's list all the pairs of segments that Vasya could choose in the first example:
Name |
---|