回文¶

回文半径¶

文字列 \(S\) が文字 \(s_i\) の前後で回文であるとき、奇数長の回文であれば前後\(r\) 個の文字で \(s_{i+r} = s_{i-r}\) が成り立つ。
\(r\) の最大値を回文半径という。最小半径は1。
言い換えると、回文半径は位置 \(i\) の前後で作れる最長回文の長さを表す。

[1]:

def palindrome_radius(S):
    rad = [1 for _ in S]
    n = len(S)
    for i in range(n):
        r = 0
        while i-r >= 0 and i+r < n and S[i+r] == S[i-r]:
            r += 1
        rad[i] = r
    return rad

例えば、文字列 “abbaaa” に含まれる奇数長回文の回文半径は次の通り。

[2]:

palindrome_radius("abbaaa")

[2]:

[1, 1, 1, 1, 2, 1]

このままでは、“abba” のような偶数回文が検出されない。

これを検出する方法として、もとの文字列の各文字間にダミー文字を挟む方法がある。

[3]:

S = "abbaaa"
T = "$" + "$".join(S) + "$"
print(T)

rad = palindrome_radius(T)
print(rad)

$a$b$b$a$a$a$
[1, 2, 1, 2, 5, 2, 1, 2, 3, 4, 3, 2, 1]

上記コードの $rad_{2i+1}$ は奇数長回文、$rad_{2i}$ (両端を除く) は偶数長回文に対応する。つまり、偶奇両方の最長回文を検出可能。

求めた回文半径 $rad_i$ は、次のようにダミー文字を含む回文半径となる。

奇数長回文 “$a$a$a$”, 回文半径4

偶数長回文 “$a$b$b$a$”, 回文半径5

ダミー文字のない回文を得るには、2文字目から1飛ばしで文字列を取り出せばよい。

回文半径を利用して、文字列の連続部分列で構成される最長の回文を $\mathcal{O}(|S|^2)$ で求めることができる。

なお、このような最長回文はManacherのアルゴリズムでより高速に求められる。

[4]:

def longest_palindrome(S):
    T = "$" + "$".join(S) + "$"
    rad = [1 for _ in T]
    n = len(T)
    for i in range(n):
        r = 1
        while i-r >= 0 and i+r < n and T[i+r] == T[i-r]:
            r += 1
        rad[i] = r

    mi = 0
    mr = 0
    for i, r in enumerate(rad):
        if mr < r:
            mi = i
            mr = r
    return T[mi-mr+1:mi+mr][1::2]

[5]:

print(longest_palindrome("mississippi"))
print(longest_palindrome("1337"))

ississi
33

Manacher¶

https://snuke.hatenablog.com/entry/2014/12/02/235837

文字列 $S$ の $i$ 番目の文字 $s_i$ に対する回文半径の配列 $r_1, r_2, \ldots, r_n$ を、計算量 $\mathcal{O}(|S|)$ で求めるアルゴリズム。

アルゴリズム¶

奇数長回文を含む文字列 “babacabac” の連続部分列を考える。
左から3文字目で回文 “aba” (半径2)、5文字目で回文 “abacaba” (半径4) が検出される。
このとき回文の対称性より、5文字目の回文判定を終えた直後に以下のことがわかる。

6文字目は 4文字目の結果(回文半径1)が3未満なので、回文半径 1
7文字目は 3文字目の結果(回文半径2)が2以上なので、回文半径 2 以上
8文字目は 2文字目の結果(回文半径2)が1以上なので、回文半径 1 以上

この場合、回文半径が定まる文字をスキップすることができる。

一般化すると次の通り。

$i$ 文字目の回文半径が $r_i$ に定まったとき、$k \in [1, r_i]$ について次のことがわかる。
- $k+r_{i-k} < r_i$ ならば、$i+k$ 文字目の回文半径は $r_{i+k} = r_{i-k}$ で確定する。$(k+r_{i+k} < r_i)$
- そうでない場合は $i+k$ 文字目の回文半径を $r_{i+k} \geq r_i - k$ とする。

実装¶

偶数長の回文を考慮して実装する。

$k+r_{i-k} < r_i$ が偽となった時点で次のステップに進んでいるが、それでも十分回文判定を減らすことができ、計算量 $\mathcal{O}(|S|)$ で求めることができる。

[6]:

def longest_palindrome(S):
    T = "$" + "$".join(S) + "$"
    rad = [1 for _ in T]
    longest = ""
    n = len(T)
    r = 1
    for i in range(n):
        r = rad[i]
        while i-r >= 0 and i+r < n and T[i+r] == T[i-r]:
            r += 1
        rad[i] = r

        # Manacher
        k = 1
        while i-k >= 0 and k + rad[i-k] < rad[i]:
            rad[i+k] = rad[i-k]
            k += 1
        if i + k < n:
            rad[i+k] = rad[i] - k
        i += k

    mi = 0
    mr = 0
    for i, r in enumerate(rad):
        if mr < r:
            mi = i
            mr = r
    return T[mi-mr+2:mi+mr:2]

[7]:

print(longest_palindrome("mississippi"))
print(longest_palindrome("1337"))

ississi
33