214. Shortest Palindrome

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        rev = s[::-1]
        n = len(s)
        for i in range(n):
            if s[0:n-i] == rev[i:]: # longest prefix substring which is palindrom 
                return rev[0:i]+s 
        return ""

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        """ tc O(N) sc O(N)
        main idea: if in t at index i we find a substring equals s, return t[:i+1]
        """
        reverse_s = s[::-1]
        ns =  s + '#' + reverse_s
        nxt = [0] * len(ns)
        pre, cur = 0,1
        while cur <len(ns):
            if ns[cur] == ns[pre]:
                nxt[cur] = pre + 1 
                cur += 1 
                pre += 1 
            elif pre > 0:
                pre = nxt[pre-1]
            else:
                cur += 1
        #print(nxt)
        #print(ns)
        max_len = nxt[len(ns)-1] # max common substring of ns's prefix and suffix 
        return reverse_s[:len(reverse_s)-max_len]+s