3923. 切分子串

【题目描述】

给定两个字符串 $S, T$，求有多少种将 $T$ 拆分为两个子串 $t_1,t_2$ 的方法，满足 $t_1$ 是 $T$ 的一段非空前缀，$t_2$ 是 $T$ 的一段非空后缀，$|t_1|+|t_2|=|T|$，且 $t_1,t_2$ 均在 $S$ 中出现过。

以下注解默认字符串下标从 $1$ 开始。

$|S|$ 表示字符串 $S$ 的长度。

$t$ 为 $T$ 的一段非空前缀，当且仅当 $1\le |t|\le |T|$，且对于任意 $i\in [1, |t|]$，都满足 $t_i=T_i$。

$t$ 为 $T$ 的一段非空后缀，当且仅当 $1\le |t|\le |T|$，且对于任意 $i\in [1,|t|]$，都满足 $t_i=T_{|T|-i+1}$。 

$s$ 在 $S$ 中出现过，当且仅当 $1\le |s|\le |S|$，且存在一个整数 $i\in [1,|S|-|s|+1]$，满足对于任意 $j\in [1, |s|]$，都有 $s_j = S_{i+j-1}$。

（仍然有问题，可以参考样例说明理解。）

【输入格式】

两行，分别包含两个由小写字母组成的字符串，表示 $S, T$。

【输出格式】

一个整数，表示答案。

【样例输入】

abaaaabccaaac
abaaac

【样例输出】

4

【样例说明】

$\rm abaaac$ 有五种拆分的方式：$\rm a+baaac$、$\rm ab+aaac$、$\rm aba+aac$、$\rm abaa+ac$、$\rm abaaa+c$。其中 $\rm baaac$ 没有在 $S$ 中出现过，所以第一种方案不合法。于是有 4 种合法的拆分。

大样例

【数据规模与约定】

对于 $100\%$ 的数据，满足 $1\le |S|\le 2000, 1\le |T|\le 150$。

【来源】

璃月港算法竞赛 T1.