问题：

  

由于任何字符串，添加最少的字符可能使其在线性时间回文结构。

我只能拿出一个O（N 2 ）解决方案。

有人可以帮助我与一个O（N）解决方案？

解决方案 还原字符串 使用修改后的克努特 - 莫里斯 - 普拉特找到最新的比赛（简单的修改是只追加原始字符串的回复字符串和len（字符串后忽略匹配）。 插入恢复字符串的无与伦比的其余部分原来的。

1和3是明显的线性和2是线性东阳克努特-莫里斯-普拉特是

The question:

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

I'm only able to come up with a O(N2) solution.

Can someone help me with an O(N) solution?

解决方案

Revert the string Use a modified Knuth-Morris-Pratt to find the latest match (simplest modification would be to just append the original string to the reverted string and ignore matches after len(string). Append the unmatched rest of the reverted string to the original.

1 and 3 are obviously linear and 2 is linear beacause Knut-Morris-Pratt is.