如果字符串是静态的，则可以使用 Manacher 算法。但本题的字符串可以动态在首位添加字符，无法使用 Manacher。
本题可以使用回文树（回文自动机）算法。该算法的时间复杂度为 \(\mathcal{O}(N)\)，但空间复杂度较差，因为其本质上是字典树。
1 回文树的关键技术
回文树的关键技术为奇偶字典树 \(+\) 后缀链跳跃。下面给出思维过程。
- 后缀链跳跃
比如在 abcb 后面插入 a，则新插入的 a 与第一个 a 之间的所有字符构成了一个回文串。
那如果是插入了 c，其不能与开头的 a 构成回文串，该怎么办呢？
可以发现上面插入 a 时，本质上就是尝试在原串的后缀回文串 bcb 左右各扩展一个字符。如果新插入的字符与上一个回文串的前一个字母相同，那这个回文串就可以向左右各扩展一个字符了。但如果不同，那我们就应该找下一个短一点的回文串进行尝试，如上面的例子中尝试扩展 bcb 失败，接下来以最后一个 b 结尾的最长回文串为 b 本身，我们再尝试扩展它，扩展成功。b 扩展成为 bcb。
我们称这个不断找最长后缀回文串的过程为后缀链跳跃。
- 奇偶字典树
我们可以用两棵字典树来存储回文串，一棵存长度为奇数的，一棵存长度为偶数的。我们可以用结点 \(0,1\) 分别表示偶数字典树和奇数字典树的根。在存储回文串时，我们只存一半。比如回文串 abccba，我们在偶数字典树上加入 \(0 \to\) c \(\to\) b \(\to\) a，这样我们从下往上读，读到 \(0\) 后再读下来就是原串。如果是 abcba，那我们在奇数字典树上加入 \(0 \to\) c \(\to\) b \(\to\) a，这样我们从下往上读再读回来，但最上面的边只读一次。
下图是 zaacaac 的存储方式：
- 建回文树
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。