【题解】Solution Set - NOIP2024集训Day58 字符串
https://www.becoder.com.cn/contest/5658
「CF1466G」Song of the Sirens
考虑对于 \(s_i\)，算钦定必须覆盖到 \(t_i\) 的匹配个数 \(f_i\)。
注意到 \(s\) 每次长度都会 \(\times ~2\) 左右，其长度在 \(O(\log |w|)\) 的时候就会超过 \(|w|\)，而在此之后 \(f_i\) 可能匹配到的字符串只会有 \(t_i\) 这一位不同。
对于后面这一部分，我们直接枚举可能的 \(t_i\)，然后在 \(w\) 的对应位置上暴力 check，这样均摊下来是 \(O(w)\) 的。
而前面这一部分，每一次 \(O(w)\) 维护 hash，同样 \(O(w)\) 算 \(f_i\)。一共 \(O(\log |w|)\) 次。
所以总时间复杂度为 \(O(w+w\log w)\)。
22min
标签：Set,log,题解,Solution,Day58,NOIP2024 From： https://www.cnblogs.com/CloudWings/p/18491738