_Nishachor's blog

Need Help!
By _Nishachor, history, 5 years ago, In English

Suppose a string s of size n is given. Now you have to answer the minimum number of characters to append at the end to make it a palindrome. How to solve this problem in O(n) time complexity?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the source of this problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://community.topcoder.com/stat?c=problem_statement&pm=10182. What I asked is kind of modified version of this problem. But the constraint of this problem is too low. So any O(n^2) brute force solution works. But how to solve this in O(n)?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The number of characters you need to append is equal to $$$n$$$ minus the length of the longest palindromic suffix. You can find this in $$$O(n)$$$ with hashing/Manacher's/something.

      Why is this true? Imagine the string as a concatenation of $$$AB$$$, where $$$A$$$ is the beginning of the string and $$$B$$$ is the longest palindromic suffix. Let $$$|x|$$$ denote the length of the string $$$x$$$. Obviously this is an upper bound to the answer, as $$$|A|$$$ = $$$n - |B|$$$ and you can just append the reverse of $$$A$$$.

      It's also a lower bound. Let's say there was some $$$C$$$ that you could append where $$$|C| < |A|$$$. Then, you can imagine the new string with appended characters like this: $$$ABC$$$, where the whole string is a palindrome. That means the string is also [reverse of $$$C$$$] + $$$DBC$$$ where $$$D$$$ is the part of $$$A$$$ that isn't part of the reverse of $$$C$$$. But this must mean that $$$DB$$$ is also a palindrome. Because $$$DB$$$ is a suffix of the string, this must mean that $$$B$$$ was not the longest palindromic suffix, and thus we have a contradiction.

      So the answer is exactly $$$|A|$$$, or for the Topcoder problem, $$$2|A| + |B|$$$.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if you want o(n) you can use KMP algoritm which take O(n) you can use it to get the longest palindrom from end of string for example: this string abcdc would be 2 because the substr 'cdc' is palindrome so we must append 2 chars . you can look to my code (https://mirror.codeforces.com/contest/1326/submission/73817581) which i use in it kmp algorithm to find prefix and suffix palindrome

hope it well

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We simply need to find the longest suffix palindrome of s.

1)Reverse the string. Let the new string be r.
2)Calculate the prefix function of r.(U can read about the same at cp-algorithms)
3)Take the maximum i such that pi[i]>=floor(i/2).

Answer is (n-i). As 1 ...... i is the longest prefix palindrome of r => n-i+1 ..... n is the longest suffix palindrome for s.

→ Reply