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

Question

Boyer-Mooreアルゴリズムをワーストケースのリニアにするには、ミスマッチテーブルの計算をO（m）にする必要があります。しかし、純粋な実装では、すべての接尾辞O（m）とその接尾辞が等しいかどうかをチェックして等価性をチェックすることができます... O（m ）です！

以下は、table building algorithmの単純な実装です。したがって、この質問は次のようになります。このアルゴリズムのランタイムをどのようにして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

this pageの "良いサフィックスヒューリスティックのための前処理"のコードは、O（n）時間内に良好なサフィックステーブルを作成します。また、コードの仕組みについても説明します。