如何在不会 ACAM 的时候通过 1008？

· · 个人记录

题目。

ACAM 直接每个节点维护 fail 树到根的最小长度就可以了。

本人不知道为什么，不会 ACAM 了。😰😰🤔🤔

发现 pref suf 的长度种类只有 \mathcal{O}(\sqrt{n}) 种，得到 \mathcal{O}(n\sqrt{n}\log n) 的做法，过不了。😅😅😂🤣

本质要处理，从 l 开始最短的在 pref 集合的串是啥。

发现把 s 后缀数组求出来，按照从小到大的字典序求，只要能找到串，串的字典序是递增的。😁😁

直接哈希（有一个部分要二分）维护。💩💩

然后我不知道为啥还写了主席树。🤨😮

因此得到这坨大便：link。🤮🤮🤮😇😇