palindrome

Use the reversed() function that comes with Python

def is_plalindrome(string):    
    return string == ''.join(list(reversed(string)))Copy the code

Their implementation

def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left] ! = string[right]: return False left += 1 right -= 1 return TrueCopy the code

And of course slice string[::-1]

The longest string of subroutines

Brute force

Brute force cracking, enumerating all substrings, judging whether each substring is palindrome, time complexity is O(n^3)

Dynamic programming

def solution(s): s = list(s) l = len(s) dp = [[0] * l for i in range(l)] for i in range(l): Dp [I][I] = True # dp[I][i-1] = True resLeft = 0 resRight = 0 # For I in range(0, l-k+1): j = I + k-1 if s[I] == s[j] and dp[I +1][j-1]: Dp [I][j] = True # if resRight + 1 < k: resLeft = i resRight = j return ''.join(s[resLeft:resRight+1])Copy the code

Time is O(n^2), space is O(n^2).

Manacher algorithm

Manacher algorithm first preprocesses the string, making all strings have odd length, inserting the same symbol and the symbol does not exist in the original string, and the palindrome of the string is not affected

aba => #a#b#a#
abab => #a#b#a#b#Copy the code

The distance between the right-most position in the palindrome string and its axis of symmetry is called the palindrome radius. Manacher algorithm defines a palindrome radius array RL, RL[I] represents the palindrome radius with the i-th character as the axis of symmetry. For the string inserted delimiter obtained above, we can get the RL array

char:  # a # b # a #
RL:    1 2 1 4 1 2 1
RL-1:  0 1 0 3 0 1 0
i:     0 1 2 3 4 5 6
char: # a # b # a # b #
RL:   1 2 1 4 1 4 1 2 1
RL-1: 0 1 0 3 0 3 0 1 0
i:    0 1 2 3 4 5 6 7 8Copy the code

We also find RL[I] -1: we find that RL[I] -1 is exactly the longest palindrome length of the initial string with position I as its axis of symmetry

So here’s how to get an RL array. You can refer to this article.

The following is the algorithm implementation

def manacher(preS):
    s = '#' + '#'.join(preS) + '#'
    l = len(s)
    RL = [0] * l
    maxRight = pos = maxLen = 0
    for i in range(l):
        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] < l and s[i - RL[i]] == s[i + RL[i]]:
            RL[i] += 1
        if i + RL[i] - 1 > maxRight:
            maxRight = i + RL[i] - 1
            pos = i
    maxLen = max(RL)
    idx = RL.index(maxLen)
    sub = s[idx - maxLen + 1: idx + maxLen]
    return sub.replace('#', '')Copy the code

Space complexity: with the help of an auxiliary array, the space complexity is O(n) time complexity: although the inner loop exists, the inner loop only runs on the unmatched parts, and only once for each character, so the time complexity is O(n).

The longest palindrome prefix

A prefix starts with the first character

The longest palindrome prefix below

abbabbc => abbc
abababb => ababa
sogou => sCopy the code

Reverse the original string, then the problem is changed to find the value of the prefix and inverse suffix of the original string and the maximum length. This problem is actually the solution of the next array in KMP algorithm

Specific solution: reverse and concatenate the original string, separate the original string and reverse with ‘#’ to avoid internal string interference.

def longest_palindrome_prefix(s):
    if not s:
        return 0
    s = s + '#' + s[::-1] + '$'
    i = 0
    j = -1
    nt = [0] * len(s)
    nt[0] = -1
    while i < len(s) - 1:
        if j == -1 or s[i] == s[j]:
            i += 1
            j += 1
            nt[i] = j
        else:
            j = nt[j]
    return nt[len(s) - 1]Copy the code

Add characters to generate the shortest palindrome string

This problem is basically the same as above, for example:

Aacecaaa -> aaACecAAA # add a abcd -> dcbabcd # add DCBCopy the code

We find the longest palindrome prefix of the string, and then the rest of the string is reversed and concatenated to the head of the string

def solution(s):
    length = longest_palindrome_prefix(s)
    return s[length:][::-1] + sCopy the code

Longest sequence of rhymes

Dynamic programming method

  • Dp [I][j] represents the longest subsequence length existing in the subsequence S [I..j]
  • Initialize dp[I][I] = 1
  • When s = = s [j] [I] is true, dp [I] [j] = dp + 1] [I] [j – 1 + 2
  • When s = = s [j] [I] is false, dp [I] [j] = Max (dp [j], [I + 1] dp [I] [1])
Def solution(s) = len(s) dp = [[0] * l for I in range(l)] for I in range(l): For I in range(0, l+1): j = I + k+1 if s[I] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) return dp[0][l-1]Copy the code

Time is O(n^2), space is O(n^2).

From: http://youbookee.com/2016/09/06/plalindrome-substring/