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

Question

Для алгоритма Бойера-Мура, который должен быть наихудшим линейным, вычисление таблицы неверного соответствия должно быть 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) времени. Он также объясняет, как работает код.