Неполное понимание построения таблицы префиксов в методе Кнута-Морисса-Пратта
Ниже одна из классических реализации построения списка префиксов. В этой реализации понятны почти все пункты, за исключением того момента когда мы в случае неравенства букв в позициях m и i и неравенства переменной m нулю, назначаем ей значение из массива по индексу на единицу меньшую: m = aux[m-1]. Почему просто его не обнулить?
def lsp_table_creator(W):
aux = [0] * len(W)
i = 1
m = 0
while i < len(W):
if W[i] == W[m]:
m += 1
aux[i] = m
i += 1
elif W[i] != W[m] and m != 0:
m = aux[m-1]
else:
aux[i] = 0
i += 1
return aux
Ответы (1 шт):
Что такое m? Это длина рассматриваемого префикса.
На каждом шаге, удлиняя суффикс, мы может получить совпадающий с ним префикс только на единицу большей длины, чем предыдущий. А может эта длина и уменьшиться, и иногда действительно до нуля. Вот только если уменьшить сразу до нуля и потом проверять по порядку все длины по нарастанию, то придётся проверять много символов. В целях оптимизации длину m уменьшают по одному, чтобы максимально переиспользовать уже имеющуюся информацию - тогда приходится использовать только одну проверку на каждое уменьшение.
Без этой оптимизации время работы станет квадратичным, а с её применением - линейным - за счёт того, что общее количество уменьшений длины префикса не превышает длины строки