Loading

CF432D Prefixes and Suffixes （kmp + 失配树）

CF432D Prefixes and Suffixes kmp + 失配树 前后缀容易想到 kmp，发现完美子串的种类显然就是 \(nxt_n\) 一直跳的次数。难点在统计每种的出现次数。 考虑连边 \(nxt_i\rightarrow i\)，构成了一个 fail 树。这棵树刻画了前后缀的包含关
posted @ 2024-06-30 15:52  Fire_Raku  阅读(1)  评论(0)  编辑  收藏  举报