読者です 読者をやめる 読者になる 読者になる

回文

アルゴリズム 文字列

回文のアルゴリズムとか

回文の判定

反転したものと一致するかを見る

def is_palindrome(s):
    return s == s[::-1]

回文の全列挙

文字列sに含まれる回文をすべて求める.
例えば,abracadabraには[a, b, c, d, r, aca, ada]がある.
これは,すべての中心となる箇所について,文字が一致する限り左右に伸ばしていけばいい.

# 文字列sの回文の集合を求める(O(N^2))
def palindromes(s):
    palindromes_set = set()

    for i in range(len(s)):
        # iを中心とした回文
        left = i
        right = i
        while 0 <= left and right < len(s) and s[left] == s[right]:
            palindromes_set.add(s[left:right + 1])
            left -= 1
            right += 1

        # iとi + 1の間中心とした回文
        left = i
        right = i + 1
        while 0 <= left and right < len(s) and s[left] == s[right]:
            palindromes_set.add(s[left:right + 1])
            left -= 1
            right += 1

    return palindromes_set


def main():
    s = "abracadabra"
    print(palindromes(s))

if __name__ == '__main__':
    main()

最長回文部分列

文字列sの部分列のうち,最も長い回文を求める.
例えば,aabbcdaaの最長回文部分列はaabbaaとなる.
これは
dp[i][j] = [i, i + j)での最長の回文の文字数
とする動的計画法で解くことができる

def longest_palindrome_subsequence(s):
    n = len(s)
    dp = [[0] * (n + 1) for i in range(n)]    # [i,i + j)での最長の回文の文字数
    for i in range(0, n):
        dp[i][1] = 1

    for j in range(2, n + 1):
        for i in range(n - j + 1):
            if s[i] == s[i + j - 1]:
                dp[i][j] = dp[i + 1][j - 2] + 2
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j - 1])

    return dp[0][-1]


def main():
    s = "aabbcdaa"
    print(longest_palindrome_subsequence(s))

if __name__ == '__main__':
    main()

Manacher

文字列sが与えられたとき,文字iを中心とする回文の半径をO(n)で求める.
例えばbcbcbaなら
123211
という配列を求めることができる.
文字列の頭良い感じの線形アルゴリズムたち2がわかりやすい

Palindromic tree

葉が回文となるような木をO(n)で構築する
Palindromic tree.に詳しい.
bbcbcbという文字列なら以下のような木が構築される.
f:id:MitI_7:20160316174700p:plain

用語

  • ノード
    各ノードは1つの回文を表す.
    特殊なノードとして回文の文字列のサイズが-1のノードと0のノードがある.

  • edge
    ノードuの両端に文字xを加えることでノードvができるとき,ノードuからノードvにxという文字つきのedgeが張られる.
    例えば,bというノードとcbcというノードがある場合,bの両端にcを加えるとcbcができるので,ノードbからノードcbcには,cという文字つきのedgeが張られる.

    • サイズが0のノードの両端にxを加えた場合,ノードxxができる.
    • サイズが-1のノードの両端にxを加えた場合,ノードxができる.
  • suffix link
    ノードuの最大の接尾辞回文がノードvとなるとき,ノードuからノードvにsuffix linkが張られる.
    例えば,bbcbcbというノードの接尾辞のうち最大の回文はbcbなので,ノードbbcbcbからノードbcbにsuffix linkが張られる.

    • サイズが1のノードのsuffix linkはサイズが0のノードとする.
    • サイズが0のノードのsuffix linkはサイズが-1のノードとする.
    • サイズが-1のノードのsuffix linkはサイズが-1のノードとする.
    • すべてのノードはsuffix linkをひとつもつ.

Palindromic treeの構築

文字列を先頭から順番に読み込みながら,「1. ノードの追加」,「2. 追加したノードへedgeを張る」,「3. 追加したノードからsuffix linkを張る」を繰り返していく.

文字列Sのpalindromic treeを作成しようとしており,接頭辞Pまでの処理が完了し,Pの次の文字xを処理しようとしているとする. またPの最大の接尾辞の回文をtとする.

  1. ノードの追加

    1. tからsuffix linkをたどり,xAxとなるようなノードAを見つける.(つまり,文字列P + xの接尾辞としてにxAxというようなAがあるか探す)
    2. xAxが新しい回文の場合ノードとして追加する
    3. xAxがすでに存在する場合,xについての処理は終わる.
  2. 追加したノードへedgeを張る

    1. ノードAからノードxAxへxという文字つきのedgeを張る.
  3. 追加したノードからsuffix linkを張る

    1. 文字列P + xの最大の接尾辞回文としてtをxAxとする.
    2. ノードAからさらにsuffix linkをたどり,xBxとなるようなノードBを見つける.
    3. xAxからxBxへsuffix linkを張る.

具体的にbbcbcbという文字列で考える.
bbcbcまで処理が完了しており,bを処理しようとしている状態とする.
このとき,最大の接尾辞回文としてノードcbcを保持している.

  1. ノードcbcの両端にbを加えた回文であるbcbcbが文字列にあるか確認する.
  2. あるので,bcbcbというノードを追加し,ノードcbcからノードbcbcbへ文字bつきのedgeを張る.
  3. ノードcbcからsuffix linkをたどり,ノードcを得る.
  4. ノードcの両端にbを加えたbcbが文字列中にあるか確認する.
  5. あるので,ノードbcbcbからノードbcbにsuffix linkを張る.

コード

問題

参考