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

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

Код в разделе " Предварительная обработка для эвристики с хорошим суффиксом " на этой странице создается таблица хороших суффиксов в Вовремя. Также объясняется, как работает код.