Блог пользователя _Nishachor

Need Help!
Автор _Nishachor, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the source of this problem?

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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|$$$.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить