-2

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

Problem

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.

Example

Given String = 'abab'

Output = 'ababa'

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.

Edited

String = 'abbcd' Output = 'abbcdcbba'

My attemp

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

My question

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

4

2 回答 2

4

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

这表明了以下算法：

找到最大的回文后缀，然后将反向子串附加到该回文后缀的左侧。这将为您提供通过在字符串末尾添加字符可获得的最短回文。

一个粗暴的实现将是O(n^2). 您可以O(n)通过使用两个滚动哈希来测试后缀是否为O(1).

以下是这些哈希如何工作的概述：

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应该是一个（小）素数，你应该做所有的计算模另一个（大）素数。为了保持它的效率，递增地计算幂，不要使用任何幂算法。您可以使用更多哈希值来避免误报。

如果我没有混淆，还有一个涉及KMP 算法的解决方案，但我不再熟悉它了。

于 2013-08-03T15:20:16.890 回答
0

一个直接的 θ(n) 方法（对于一个 n 字符的输入字符串 S）是在 θ(n) 时间内为 S 构建一个后缀树T。令R =反向（S）。在时间 O(n) 内，使用 T 在 S 的后缀中找到 R 的最长匹配。假设最长匹配有 m 个字符；即R的前m个字符匹配S的最后m个，m是最大的。令 P 为 R 的最后一个 nm 字符，或 S 的第一个 nm 的倒数。所需的结果是 S + P。

于 2013-08-03T18:27:28.373 回答