回文の判定

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

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
という配列を求めることができる．
文字列の頭良い感じの線形アルゴリズムたち２がわかりやすい

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. tからsuffix linkをたどり，xAxとなるようなノードAを見つける．（つまり，文字列P + xの接尾辞としてにxAxというようなAがあるか探す）
2. xAxが新しい回文の場合ノードとして追加する
3. xAxがすでに存在する場合，xについての処理は終わる．
追加したノードへedgeを張る
1. ノードAからノードxAxへxという文字つきのedgeを張る．
追加したノードからsuffix linkを張る
1. 文字列P + xの最大の接尾辞回文としてtをxAxとする．
2. ノードAからさらにsuffix linkをたどり，xBxとなるようなノードBを見つける．
3. xAxからxBxへsuffix linkを張る．

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

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

Eating Your Own Cat Food

回文