Cage 字符串听课笔记

困困困！ KMP 注意到 KMP 的复杂度是均摊的，那么是否可以绕开？ 注意到 KMP 实际上一个串的 ACAM，那么考虑可以类似的，在加入一个字符的同时维护 ACAM（考虑 ACAM 的构建过程，前面的点不会被影响）那么每次就可以通过 \(O(|\Sigma|)\) 的修改（或者利用可持久化数据结
posted @ 2023-12-29 21:35  jeefy  阅读(10)  评论(0)  编辑  收藏  举报