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

Question

问题:

Given any string, add the least amount of characters possible to make it a palindrome in linear time.

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

有人可以帮我解决 O(N) 问题吗？

Answer 1

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

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