1006. 三串共鸣

题目描述

给定三个仅由小写英文字母组成的字符串 $a$，$b$ 和 $c$。所有字符串的下标均从 $0$ 开始，我们用 $|S|$ 表示字符串 $S$ 的长度，$S[x..y]$ 表示字符串 $S$ 从下标 $x$ 到下标 $y$ 的连续子串，区间两端均包含在内。

你需要统计有多少个三元组 ($i,j,l)$ 满足以下条件：

1. $0 \le l < |a|$，$0 \le i < |b|$，$l \le j < |c|$；
2. 在字符串 $b$ 中 至少存在一个 起始位置 $k$（$0\le k$ 且 $k+l<b$），满足 $a[0..l] = b[k..k+l] = c[j-l..j]$ 且位置 $i$ 被这个匹配子串覆盖，即 $k \le i \le k+l$。

换句话说，对于每个 $l$ 和 $j$，如果 $a$ 的长度为 $l+1$ 的前缀等于 $c$ 中以 $j$ 结尾、长度为 $l+1$ 的子串，那么我们记这个字符串为目标串。接着在 $b$ 中寻找所有等于该目标串的子串，并统计这些子串覆盖到的不同位置 $i$ 的数量。

注意，$b$ 中可能存在多个相同的匹配子串。如果它们覆盖了同一个位置 $i$，那么对于当前固定的$（j,l$），这个位置 $i$ 只能贡献一次。

输入格式

第一行一个正整数 $T$（$1\le T\le 10^4$），表示数据组数。

对于每组数据，第一行三个整数 $n_a,n_b,n_c$（$1\le n_a,n_b,n_c\le 10^5$），分别表示三个字符串的长度。

接下来三行，每行一个仅由小写英文字母构成的字符串，分别表示给定的字符串 $a$，$b$ 和 $c$。

对于所有数据，保证 $\sum (n_a+n_b+n_c)\le 3\times 10^6$。

输出格式

对于每组数据，输出一行一个整数，表示满足条件的三元组的总数。

样例输入

2
2 3 3
ab
bab
abc
4 5 6
aaaa
aaaaa
aaaaaa

样例输出

3
90

提示

对于第一组样例，满足条件的三个三元组分别为：($1,0,0$)，($1,1,1$) 和 ($2,1,1$)。

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1006