Вычисление второй (несоответствующей) таблицы в алгоритме поиска строки Бойера-Мура

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

Код в разделе «Предварительная обработка для эвристики хорошего суффикса» на на этой странице создает таблицу хороших суффиксов за O (n) времени. Также объясняется, как работает код.