Algorithm for expanding to the shortest palindrome by adding characters at the end of a line

Question

I found one problem with the algorithm. I solved this problem, but I want to optimize it. I am asking the same problem here.

Problem

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

Example

Given String = 'abab'

Exit = 'ababa'

Rationale: The ababa string contains the abab string, starting at the beginning and at the end of the line, with only 1 extra character at each end.

Edited

String = 'abbcd' Exit = '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 so, what is the algorithm? (Give me a hint)

Answer 1

Please note that in the palindrome all pairs of characters with equal distance to the middle of the line are equal.

This suggests the following algorithm:

Find the largest palindrome suffix, then add the back of the substring to the left of this palindrome suffix. This will give you the shortest palindrome you can get by adding characters to the end of the line.

A rough implementation of this would be O(n^2) . You can get O(n) with two rolling hashes to check if the suffix is ​​a palindrome in O(1) .

It describes 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) 

Where p should probably be (small-ish) simple, and you should do all the calculations for another (large-ish) simple. To maintain efficiency, calculate the power gradually, do not use the exponential algorithm. You can use more hashes to avoid false positives.

If I don’t mess things up, there is also a solution that includes the KMP algorithm, but I am no longer familiar with it.

Answer 2

The direct approach θ (n) (for the input string S of an n-character) is to construct an entity tree for S, in θ (n) time. Let R = inverse (S). For O (n), use T to find the longest match for R among the suffixes S. Assume that the largest match has m characters; those. the first m characters in R correspond to the last m of S, and m to the maximum. Let P be the last nm of characters of R or the reverse side of the first nm of S. The desired result is S + P.