5159. 前缀分割

单点时限: 1.0 sec

内存限制: 256 MB

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

如果 $|S|=n$ ,那么我们可以把 $S$ 记作 $s_1s_2\cdots s_n$ ,其中 $s_i(1\le i\le n)$ 表示 $S$ 的第 $i$ 个字符。

在此基础上,对于任意的 $1\le l\le r\le n$,我们定义 $S(l,r)$ 表示 $S$ 的子串,它是形如 $s_ls_{l+1}s_{l+2}\cdots s_{r}$ 的字符串。

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

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

你需要求解出:

$$
\sum_{1\le l\le r\le |C|} F(l,r)
$$

输入格式

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

输出格式

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

样例

Input
aba
baaba
abbaa
Output
4

提示

【样例解释】

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

【数据范围】

$1\le |A|,|B|,|C|\le 10^6$ 。所有出现的字符均为小写英文字母。

16 人解决,26 人已尝试。

19 份提交通过,共有 107 份提交。

5.9 EMB 奖励。

创建: 1 年,5 月前.

修改: 1 年,5 月前.

最后提交: 7 月前.

来源: N/A

题目标签