Boyer-Moore文字列検索アルゴリズムの2番目の（ミスマッチ）テーブルの計算

Question

ボイヤームーアアルゴリズムが最悪の場合の線形になるには、不一致テーブルの計算はO（m）でなければなりません。ただし、単純な実装では、すべてのサフィックスO（m）をループし、そのサフィックスのすべての位置に移動して、等しいかどうかをチェックできます。これはO（m ³ ）です！

以下は、テーブル構築アルゴリズムの素朴な実装です。したがって、この質問は次のようになります：このアルゴリズムのランタイムをO（m）に改善するにはどうすればよいですか？

def find(s, sub, no):
    n = len(s)
    m = len(sub)

    for i in range(n, 0, -1):
        if s[max(i-m, 0): i] == sub[max(0, m-i):] and \
            (i-m < 1 or s[i-m-1] != no):
            return n-i

    return n

def table(s):
    m = len(s)
    b = [0]*m

    for i in range(m):
        b[i] = find(s, s[m-i:], s[m-i-1])

    return b

print(table('anpanman'))

心を休めるために、これは宿題ではありません。誰かが改善のためのアイデアを投稿したら改訂版を追加します。

Answer 1

<！> quot;のコード、良好なサフィックスヒューリスティックの前処理<！> quot; このページでは、サフィックステーブルを作成します。定刻。また、コードの仕組みについても説明します。