2026 Summer Day20

CF1200 E - Compress Words

每次枚举可以匹配的长度 $j$ ，然后使用 hash 判断两个字符串切片是否相等。复杂度 $O(\sum |S|)$ 。

考虑暴力枚举修改的位置的前后 $50$ 个位置的状态，然后使用手写 hash 表暴力合并信息，单次修改复杂度 $O(k^2)$ ，可以使用链表维护前后位置关系。查询的时候遍历 $s$ 的每一个长度为 $k$ 的子串，单次查询复杂度 $O(|S|)$ 。

蒟蒻在这道题中第一次手写 hash 表，直接被肘飞了，还以为自己写错了，后来才发现是自己的模数太烂了，有没有神秘模数技巧。