4

ボイヤームーアアルゴリズムが最悪の場合の線形であるためには、不一致テーブルの計算はO（m）でなければなりません。ただし、単純な実装では、すべての接尾辞O（m）がループされ、その接尾辞のすべての位置が等しくなるかどうかがチェックされます...これはO（m 3）です。

以下は、テーブル作成アルゴリズムの単純な実装です。したがって、この質問は次のようになります。このアルゴリズムの実行時間を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'))

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

4

1 に答える 1

1

このページの「good-suffixヒューリスティックの前処理」の下のコードは、O（n）時間でgood-suffixテーブルを作成します。また、コードがどのように機能するかについても説明します。

于 2009-05-09T14:50:32.487 に答える