回文判定 Manacher in Python

manacher

線形時間で回文判定ができる。(判定するリストまたは文字列に&が入っていたら違う文字や数字に書き換えて使う)
このアルゴリズムは同じ文字列やリストについて、複数回、複数区間の回文判定を行うときに強い。
まず線形時間でself.r配列を作って、その後の判定については定数時間で動きます。
判定回数がO(n)だった場合、普通に実装するとO(n^2)となってとても間に合わないが、manacherではO(n)でmake_rしたのち、定数時間の判定をO(n)回するので全体でO(n)で済む。

manacher.py

"""Module for palindrome."""


class manacher:
    """Cache radius array of palindrome to judge in linear time."""

    def __init__(self, l):
        """Insert '&' to judge both even and odd length palindrome."""
        self.n = len(l)
        self.m = 2*self.n+1
        self.d = ['&']*self.m
        self.r = [0]*self.m
        for i in range(self.n):
            self.d[2*i+1] = l[i]
        self.make_r()

    def make_r(self):
        """Make self.r[i] (radius of palindrome whose center is self.d[i])."""
        i, j = 0, 0
        while i < self.m:
            while j <= i < self.m-j and self.d[i-j] == self.d[i+j]:
                j += 1
            self.r[i] = j
            k = 1
            while k <= i < self.m-k and k+self.r[i-k] < j:
                self.r[i+k] = self.r[i-k]
                k += 1
            i += k
            j -= k

    def judge(self, start, end):
        """Return 1 if l[start, end) is a palindrome."""
        center = start+end
        return 2*end-1 < center+self.r[center]

使用例

l=[1, 0, 0, 0, 1, 2]
s = manacher(l)
for i in range(6):
    for j in range(i+1, 7):
        print(l[i:j], s.judge(i, j))

実行結果

[1] True
[1, 0] False
[1, 0, 0] False
[1, 0, 0, 0] False
[1, 0, 0, 0, 1] True
[1, 0, 0, 0, 1, 2] False
[0] True
[0, 0] True
[0, 0, 0] True
[0, 0, 0, 1] False
[0, 0, 0, 1, 2] False
[0] True
[0, 0] True
[0, 0, 1] False
[0, 0, 1, 2] False
[0] True
[0, 1] False
[0, 1, 2] False
[1] True
[1, 2] False
[2] True

引数start, endに対して[start, end)区間が回文になっているかどうかを返します。

追記

self.dの比較のところを奇遇で場合分けしてあげれば無駄なメモリを使わなくて済みそう

manacher.py

def make_r(self, l):
        """
        Make self.r whose length is self.m.

        if l="01221" then considering "&01&2&2&1&" (=l_ temporarily)
        self.r[i] is radius of palindrome whose center is l_[i].
        """
        i, j = 0, 0
        while i < self.m:
            while j <= i < self.m-j and self.compare(l, i-j, i+j):
                j += 1
            self.r[i] = j
            k = 1
            while k <= i < self.m-k and k+self.r[i-k] < j:
                self.r[i+k] = self.r[i-k]
                k += 1
            i += k
            j -= k

def compare(self, l, left, right):
    """If left%2=1 then compare l[left//2] with l[right//2]."""
    return l[left//2] == l[right//2] if left & 1 else True