16 人解决,26 人已尝试。
19 份提交通过,共有 107 份提交。
5.9 EMB 奖励。
单点时限: 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$ 。
一行,一个整数,表示你的答案。
aba baaba abbaa
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