2023 年上海市大学生程序设计竞赛 - 六月赛

D. 前缀分割

单点时限: 1.0 sec

内存限制: 256 MB

对于一个字符串 S ,我们定义 |S| 表示它的长度。

如果 |S|=n ,那么我们可以把 S 记作 s1s2sn ,其中 si(1in) 表示 S 的第 i 个字符。

在此基础上,对于任意的 1lrn,我们定义 S(l,r) 表示 S 的子串,它是形如 slsl+1sl+2sr 的字符串。

现在给出三个字符串:A,B,C

定义 F(l,r) 表示子串 C(l,r) 拆分成 A 的一个前缀拼接上 B 的一个前缀的方案数。形式化来说,F(l,r) 表示有多少对 i,j(1i|A|, 1j|B|) ,满足 C(l,r)=a1a2aib1b2bj

你需要求解出:

1lr|C|F(l,r)

输入格式

一共三行,三个字符串,分别表示 A,B,C

输出格式

一行,一个整数,表示你的答案。

样例

Input
aba
baaba
abbaa
Output
4

提示

【样例解释】

仅有子串 ab,abb,abba,abbaa 可以被拆成 A 串的前缀接上 B 串的前缀的形式,而且这些子串的拆分方案数都是 1 ,因此答案是 4

【数据范围】

1|A|,|B|,|C|106 。所有出现的字符均为小写英文字母。