KMP

各位置までの文字列について「接頭辞と接尾辞が一致する最大の長さ」（失敗関数）を求め、それを使って文字列検索をします。文字列だけでなく、整数のリストなどにも使えます。

• prefix_function(s): pi[i] が「s[:i + 1] の接頭辞と接尾辞が一致する最大の長さ（s[:i + 1] 自身は除く）」であるリストを返す。 $O(N)$

• find_all(t, p): $t$ の中で $p$ が現れる位置（先頭の添字）を昇順のリストで返す（ $p$ は空でないこと）。重なりも数える。 $O(

  t

  +

  p

  )$

• min_period(s): すべての $i$ で s[i] == s[i + p] となる最小の $p$。 $O(N)$

min_period(s) が $N$ を割り切るとき、 $s$ は長さ $p$ の文字列の繰り返しです。

コード

def prefix_function(s):
    # pi[i] = s[:i + 1] の接頭辞と接尾辞が一致する最大の長さ（s[:i + 1] 自身は除く）
    n = len(s)
    pi = [0] * n
    k = 0
    for i in range(1, n):
        while k and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi


def find_all(t, p):
    # t の中で p が現れる位置（先頭の添字）のリスト。p は空でないこと
    pi = prefix_function(p)
    res = []
    k = 0
    for i, c in enumerate(t):
        while k and c != p[k]:
            k = pi[k - 1]
        if c == p[k]:
            k += 1
        if k == len(p):
            res.append(i - k + 1)
            k = pi[k - 1]
    return res


def min_period(s):
    # すべての i で s[i] == s[i + p] となる最小の p
    return len(s) - prefix_function(s)[-1] if s else 0