214.md

Shortest Palindrome

Description

link

---

Solution

find the longest palindrome substring starts from index 0

KMS table:

a b a b c
0 0 1 2 0

Example:

input:

"catacb"

Temp String:

"catacb # bcatac"

KMP table:

c a t a c b # b c a t a c

0 0 0 0 1 0 0 0 1 2 3 4 5

In the last cell, we got a value 5. It means in s we have a substring of length 5 that is palindrome.

---

Code

O(n)

class Solution:
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        kms_table = [0]
        
        def prefix(s):
            match_len = 0
            for i in range(1, len(s)):
                while match_len > 0 and s[i] != s[match_len]:
                    match_len = kms_table[match_len - 1]
                match_len = match_len + 1 if s[i] == s[match_len] else 0
                kms_table.append(match_len)
        
        prefix(s + "#" + s[::-1])
        return s[kms_table[-1]:][::-1] + s