[2021][01]Longest Palindrome Substring

問題情報

問題の概要

問題では,与えられた文字列sにおいてsの中で最も長いパリンドロン部分の文字列を返す非常に簡単な問題が望ましい.

せいげんじょうけん

1<=文字列sの長さ<=1000

文字列sは、英語の小文字または大文字からなる

質問へのアクセス

Brute Forceで解く方法があります.これは、iの1文字目を中心とした最長部分の文字列をダブルfor文で検索する方法です.この方法で解くと100%タイムアウトになります.

次の方法は動的プログラミングを用いてBrute Forceで繰り返される部分を処理することである.アルゴリズム名はManacherアルゴリズムです.

iの2番目のインデックスを中心とした最長レコーダ長がA配列に格納される.

j

文字列sの先頭から末尾までループし、Aの値を初期化する.以下は初期化ルールです.

i<=rはA[i]=min(r-i,A[2*p]-1])

を表す.

i<=rとは、j

i>rはA[i]=0

を表す.

i>rは、pを中心とした最長のパリンドロン部分文字列の右端において、右端よりも右端であり、これまで計算されたA値は使用できないことを意味する.

Aを初期化した後、s[i-A[i]-1]=s[i+A[i]+1の間にiを増加し続ける.

すべての文字列

を巡回した後、Aで最大値のmaxIndexが見つかった場合、maxIndexを中心としたpalindromは、見つかった最も長いpalindrom夫婦文字列になります.

偶数の長さの文字列の中でManacherアルゴリズムを使用して最も長いパリンドロン部分の文字列が見つからない.したがって、指定された文字列sの間に"#"または"@"を追加する場合、Manacherアルゴリズムを使用して正しい答えを見つけることができます.

コード#コード#

class Solution:
    def longestPalindrome(self, s: str) -> str:
    
    
        def addSharp(string) -> str:
            result = '#'
            for ss in string:
                result += ss + '#'
            return result
        
        def manacher(string) -> str:
            sharped = addSharp(s)
            a = [0] * len(sharped)
            p = r = 0
            for i in range(len(sharped)):
                if i <= r:
                    a[i] = min(r - i, a[2 * p - i])
                else:
                    a[i] = 0
                    
                while i - a[i] -1 >= 0 and i + a[i] + 1 < len(sharped) and sharped[i - a[i] - 1] == sharped[i + a[i] + 1]:
                    a[i] += 1
                
                if r < i + a[i]:
                     # r은 반지름이 아니라 i 번째 문자를 중심으로 하는 가장 긴 팔린드롬의 가장 길이
                    r = i + a[i]
                    p = i
            maxIndex = a.index(max(a))
            answer = sharped[maxIndex-a[maxIndex]:maxIndex+a[maxIndex] + 1].replace('#', '')
            return answer
        
        return manacher(s)