概要

文字列探索アルゴリズム。

ある文字列\(T\)について、\(N\)個の文字列\(s_1, s_2, ..., s_N\)の中からマッチする(最長の)文字列を線形に探索することができる。

計算量

\(O(|T| + \sum_i |s_i|)\)

実装

# この実装のnodeの説明
#
# node[0] ~ node[25]:
#     'a' ~ 'z'が来た時の次のnode (failure関数の遷移先も含まれる)
# node[-3] (node[27]):
#     いずれかの文字の終端であるかを示す(1 = 終端である)
# node[-2] (node[28]):
#     このnodeが何文字目に位置するかを表す
# node[-1] (node[29]):
#     このnodeでfailureした時の遷移先

from collections import deque
base = ord('a')
root = [None]*30
root[-2] = 0; root[-3] = 0

# 文字列sの追加
def add(s):
    node = root
    for c in s:
        code = ord(c) - base
        child = node[code]
        if not child:
            node[code] = child = [None]*30
            child[-2] = node[-2] + 1
            child[-3] = 0
        node = child
    node[-3] = 1

# BFSでfailure関数のリンクを構築
def suffix():
    que = deque([root])
    while que:
        v = que.popleft()
        for i in range(26):
            if not v[i]:
                if v[-1]:
                    v[i] = v[-1][i]
                else:
                    v[i] = root[i] or root
                continue
            if v[-1]:
                v[i][-1] = v[-1][i]
            else:
                v[i][-1] = root
            que.append(v[i])
    root[-1] = root

Verified

Pythonだと重くてつらい

  • AtCoder: "JAG Practice Contest for ACM-ICPC Asia Regional 2017 - H問題: Separate String": source (PyPy3, TLE)

参考ページ