# Short Python codes, Discuss on 2 Methods, both O(n) time

• Our goal is to find the longest palindrome starting from the first index.

1st method:
Concatenate the input string with its reverse by a special character, i.e. '\$'. Then we find the longest palindrome from the first index by finding the prefix suffix (see kmp algorithm) at the last index.

``````def LPS(p):
lps = [0] * len(p)
l = 0
for i in range(1, len(p)):
while l > 0 and p[i] != p[l]:
l = lps[l-1]
if p[i] == p[l]:
l += 1
lps[i] = l
return lps

def shortestPalindrome(s):
lps = LPS(s+'\$'+s[::-1])
return s[lps[len(lps)-1]:len(s)][::-1] + s
``````

But this method will not work if our input string also contains that special character. Another method to get around this is to use KMP matching. Consider i going from first index to the right as the index for the pattern, and j goes from the last index to the left as the index in the string to match in KMP.

``````def LPS(p):
lps = [0] * len(p)
l = 0
for i in range(1, len(p)):
while l > 0 and p[i] != p[l]:
l = lps[l-1]
if p[i] == p[l]:
l += 1
lps[i] = l
return lps

def shortestPalindrome(s):
lps = LPS(s)
i = 0; j = len(s)-1
while i < j:
while i > 0 and s[i] != s[j]:
i = lps[i-1]
if s[i] == s[j]:
i += 1
j -= 1
return s[(i+j)+1:len(s)][::-1] + s``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.