属实自闭。感觉周末要铁。
| A | B | C | D | E | F | G | H | I | J | K | L | M |
| $\varnothing$ | $\varnothing$ | $\varnothing$ | O | $\varnothing$ | O |
其实就是要求 $S[1 \dots i]$($ i \in [1, L]$) 和 $S[j \dots n]$($j \in [R, n]$) 拼接后有多少个 $T$。
用哈希预处理出 $ok_pre[i][len]$ 表示串 $S$ 以 $i$ 结尾长度为 $len$ 与 $T[1 \dots len]$ 是否相等。
$sumpre[i][len]$ 表示前缀 $i$ 中有多少长度为 $len$ 的子串与 $T[1 \dots len]$ 相等。
$anspre[i]$ 表示 $sumpre[j][m]$ 的前缀和。
那么 $[1, L]$ 中出现串的个数对答案的贡献就为 $anspre[L] \times (n - R + 1)$。
右半部分同理可以处理出 $suf$ 数组。
两端拼起来的贡献为 $\sum_{i = 1}^{m - 1} sumpre[L][i] \times sumsuf[R][m - i]$
原文：https://www.cnblogs.com/Mrzdtz220/p/11768843.html