我发现一个算法问题。我解决了这个问题，但我想，以优化。我问同样的问题在这里。

I found one algorithm problem. I solved that problem, but I want to optimize that. I ask the same problem here.

问题

一个字符串，并给出该字符串的长度 N'LT; =千万。该字符串的所有字符从'a'到'Z'。现在我们要计算最小的回文，我们可以通过添加人物到底有从给定的字符串。

One String is given and the length of that string is N <= 10000000. All characters of that string is from 'a' to 'z'. Now we have to calculate smallest palindrome that we can make from given string by adding characters the end.

示例

由于字符串=ABAB

输出='巴'

推理：字符串巴包含字符串 ABAB 从的开始和字符串的结尾开始，与只有1个额外的字符的每一端。​​

Reasoning: the string ababa contains the string abab starting from both the beginning and end of the string, with only 1 extra character on each end.

编辑

字符串='abbcd 输出='abbcdcbba

String = 'abbcd' Output = 'abbcdcbba'

我学尝试

我可以在O解决这个问题（N ^ 2）的复杂性。

I can solve this problem in O(N^2) complexity.

我的提问

我可以解决这个问题，在不到O（N ^ 2）的时间？ ，如果是的话，比什么是算法？ （给我一个提示）

Can I solve this problem in less than O(N^2) time ? , If yes, than what is the algorithm? (Give me a hint)

推荐答案

请注意，在回文中，所有对字符与字符串中间的一个相等的距离是相等的。

Note that in a palindrome, all pairs of characters with an equal distance to the middle of the string are equal.

这表明，下面的算法：

找到最大的回文后缀，然后追加子的反向本回文后缀的左侧。这将让您通过添加字符的字符串末尾最短的回文获得的。

Find the largest palindromic suffix, then append the reverse of the substring to the left of this palindromic suffix. This will get you the shortest palindrome obtainable by adding characters to the end of the string.

一个强力执行，这将是为O（n ^ 2）。你可以得到 O（N）通过使用两个滚动哈希测试一个后缀是回文O（1）。

A brute implementation of this will be O(n^2). You can get O(n) by using two rolling hashes to test if a suffix is a palindrome in O(1).

下面是这些哈希值是如何工作的一个概括：

Here's an outline of how these hashes work:

hForward(suff)  = suff[0] * p^0 + suff[1] * p^1 + ... + suff[k] * p^k
hBackward(suff) = suff[k] * p^0 + suff[k-1] * p^1 + ... + suff[0] * p^k

When adding a new character to the suffix:
Note that this is added to the beginning, since we should iterate the suffixes
from right to left.
hForward(c + suff) = c * p^0 + p * hForward(suff)
hBackward(c + suff) = hBackward(suff) + c * p^(k + 1)  

其中， P 也许应该是一个（小ISH）总理，你应该做的所有mod另一个（肥胖型）主要的计算。为了保持高效率，计算的力量逐渐，不使用任何指数算法。您可以使用更多的哈希值，以避免误报。

Where p should probably be a (small-ish) prime and you should do all the computations mod another (large-ish) prime. In order to keep it efficient, compute the powers incrementally, don't use any exponentiation algorithm. You can use more hashes to avoid false positives.

如果我没有混乱的东西，也有涉及的 KMP算法，但我并不真正熟悉它了。

If I'm not confusing things, there is also a solution involving the KMP algorithm, but I am not really familiar with it anymore.