How to Find Palindromic Substrings?

回文に関連する実装が苦手です。

回文について考えなければならないときはいつも気が重かったのですが、与えられた文字列から回文となる部分文字列を列挙する方法を@nico_shindanninさんがニコニコ生放送で解説していらっしゃいました。とても分かりやすい解説だったので、メモとしてまとめました。

次の文字列を考えてみます。

例えば先頭から5文字の部分文字列、CBABCは回文になっています。同様に、どのくらいの部分文字列が回文になっているでしょう? まずナイーブなO(N³)を実装して確かめてみました。

def palindromes(s):
    size = len(s)
    for i in range(size):
        for j in range(i, size):
            l, u = i, j
            while l <= u:
                if s[l] != s[u]:
                    break
                l += 1
                u -= 1
            else:
                yield s[i:j+1]

これはとても直感的な実装です。

部分文字列を列挙し
回文であるかどうか

を調べています。

この実装の動作を図示すると次のようになります。回文となる文字列の数は意外と多く、9個ありました。

さて、続いては@nico_shindanninさんが紹介していた方法です。回文の性質をうまく利用して、部分文字列の中央から広げて行くようにチェックを行うことによって計算量をO(N²)に落としています。

def palindromes(s):
    size = len(s)
    for i in range(size):
        l = u = i
        while 0 <= l and u < size:
            if s[l] != s[u]:
                break
            yield s[l:u+1]
            l -= 1
            u += 1

        l, u = i, i + 1
        while 0 <= l and u < size:
            if s[l] != s[u]:
                break
            yield s[l:u+1]
            l -= 1
            u += 1