单点时限: 1.0 sec
内存限制: 256 MB
对于一个字符串 S ,我们定义 |S| 表示它的长度。
如果 |S|=n ,那么我们可以把 S 记作 s1s2⋯sn ,其中 si(1≤i≤n) 表示 S 的第 i 个字符。
在此基础上,对于任意的 1≤l≤r≤n,我们定义 S(l,r) 表示 S 的子串,它是形如 slsl+1sl+2⋯sr 的字符串。
现在给出三个字符串:A,B,C。
定义 F(l,r) 表示子串 C(l,r) 拆分成 A 的一个前缀拼接上 B 的一个前缀的方案数。形式化来说,F(l,r) 表示有多少对 i,j(1≤i≤|A|, 1≤j≤|B|) ,满足 C(l,r)=a1a2⋯aib1b2⋯bj 。
你需要求解出:
∑1≤l≤r≤|C|F(l,r)
一共三行,三个字符串,分别表示 A,B,C 。
一行,一个整数,表示你的答案。
aba baaba abbaa
4
【样例解释】
仅有子串 ab,abb,abba,abbaa 可以被拆成 A 串的前缀接上 B 串的前缀的形式,而且这些子串的拆分方案数都是 1 ,因此答案是 4 。
【数据范围】
1≤|A|,|B|,|C|≤106 。所有出现的字符均为小写英文字母。