添加最少量的字符以构成回文

Question

问题:

给定任何字符串,添加尽可能少的字符,使其成为线性时间的回文.

我只能想出一个O(N ²)解决方案.

有人可以用O(N)解决方案帮助我吗？

Answer 1

1. 恢复字符串
2. 使用修改后的Knuth-Morris-Pratt查找最新匹配项（最简单的修改是将原始字符串附加到还原的字符串并忽略 len(string) 之后的匹配项）。
3. 将不匹配的其余恢复字符串附加到原始字符串。

1 和 3 显然是线性的，而 2 是线性的，因为 Knuth-Morris-Pratt 是。