sol? csp-s 2025 t3

口胡做法。

为什么场上我会觉得 $O(L|\Sigma|)$ 过不去？？？

首先根据数据范围会发现描述里的「子串 $y$ 的位置不同」是没用的。

把 $t_{i,1}$ 和 $t_{i,2}$ 分别变成形如 $x+y_1+z$ 和 $x+y_2+z$ 的形式，其中 $x$ 是 $t_{i,1}$ 和 $t_{i,2}$ 的 LCP，$z$ 是 $t_{i,1}$ 和 $t_{i,2}$ 的 LCS。

然后可以发现对于一个 $t_i$，合法的 $s$ 一定是形如 $x'+y_1+z'$ 和 $x'+y_2+z'$ 的形式，其中 $x'$ 是 $x$ 的后缀，$z'$ 是 $z$ 的前缀。

然后场上对着这个瞪了大概 2h 还是只会 $O(L^2)$ 枚举前后缀。

大概 17:10 想到可以把所有 $y_1,y_2$ 相同的拿出来一起处理，对于这些 $y_1,y_2$ 相同的字符串，把 $s_i$ 变成 $x'+\texttt{'\#'}+z'$，$t_i$ 变成 $x+\texttt{'\#'}+z$，这样就变成了 $t_i$ 中为 $s_i$ 的子串个数，用 ACAM 维护。

然后我觉得这个过不去 5e6 并且写起来还很大就没去继续想（）

大概 18:00 算了一下发现 $L\times |\Sigma|$ 约是 $1.5\times 10^8$，应该是能过的，但没时间写了（）

我场上在干什么？？？气笑了

upd：哈希写寄了，AC submission