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