Квадратичный алгоритм Кнута-Морриса-Пратта

Question

В алгоритме Кнута-Морриса-Пратта, когда слово «подстрока» представляет собой последовательность одной и той же буквы, например. «AAAAAAAA ...», таблица отказов это что-то вроде этого: «-1, 0, 1, 2, 3, 4, 5, ...».

Это означает, что если тест что-то вроде «AAAAAAAB» Когда мы достигнем «B» мы вернемся X символов и начать пытаться соответствовать снова, хотя мы знаем, что мы должны начать после того, как Б.

Am I что-то не хватает?

Edit (делая пример конкретных):

Скажем тест: AAAAAAAABAAAAAAAAA, то есть (8 As, В, 9 В) и слово ищет является AAAAAAAAA, то есть (9 As).

Нерабочее таблица будет: -1, 0, 1, 2, 3, 4, 5, 6, 7.

В какой-то момент она будет т = 0, г = 8. Это произойдет сбой , поэтому m станет m = m + i - T [8] = 0 + 8 - 7 => m = 1, а i будет T [8] = 7.

Это не сработает снова, так что теперь мы будем имеют m = 2, i = 6, а затем m = 3, i = 7 и т. д.

Answer 1

Вы вернетесь обратно length(needle) символов, но вы начнете только согласовывать их со смещением, заданным таблицей сбоев. В этом случае, если есть 7 A, и вы терпите неудачу на B, T[7] скажет «пропустить 7 символов», поэтому вы проверяете needle[7] по сравнению с haystack[failed-length(needle)+7] (где не указан индекс стога сена, где B в игле по сравнению с A). Следовательно, он будет работать в линейном времени, всегда пропуская сравнение для 6 из 7 A, которые вы уже сопоставили. Разумный алгоритм, вероятно, может пропустить немного больше, но только константы стоят больше, поскольку он не может быть лучше, чем линейный.