longest palindromic substring

Longest Palindromic Substring

Manacher algorithm
https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

brute-force solution:
for each substringin string s, check if it is palidromic
time plexity O(n^3)

two pointer solution:
improve brute-force solution
for each char c in s, since a palidormic string`s is symmetical, so we can use two pointer
left pointer at c-1 and right pointer at c+1, return False if s[left] != s[right] while left > -1 and right < len(s)
time complexity is O(n^2)

Manacher Solution:
problem of two pointer solution

  1. compare smae char multiple time
        for a string "aaa"
            the first char 'a' need to compare 2 time, firts time at first a, second time use middle a as central
    2. for palidromic string with odd / even length it need different way to handle
to improve these problem
    1. add a char not exist as seperator, so all palidormic string have odd length
        "aaa" -> "#a#a#a#"(7)
        "aa" -> "#a#a#"(5)
    2. store current max right distance(maxd) it can achieved by a char a as middle point
        for a new char c at position cp, it must at right of a
        if cp > maxd：
            use c as middle point, until its not palidormic
        else:
            length of palidormic use c as middle >= length of palidormic use c' as middle 
            where c' is the pointer symmetical to c use a as middle point

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class :
    """
    @param s: input string
    @return: the longest palindromic substring
    """
    def longestPalindrome(self, s):
        
        s='#'+'#'.join(s)+'#'
    
        RL=[0]*len(s)
        MaxRight=0
        pos=0
        MaxLen=0
        MaxString = ""
        for i in range(len(s)):
            if i<MaxRight:
                RL[i]=min(RL[2*pos-i], MaxRight-i)
            else:
                RL[i]=1
            while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
                RL[i]+=1
            #更新MaxRight,pos
            if RL[i]+i-1>MaxRight:
                MaxRight=RL[i]+i-1
                pos=i
            if RL[i] > MaxLen:
                MaxLen=RL[i]
                MaxString = s[pos-(MaxRight-pos)+1:MaxRight]
        MaxString = MaxString.replace("#","")
        return MaxString