Алгоритм поиска шаблона KMP

Question

Я понял алгоритм KMP, то есть концепцию сохранения значения для суффикса соответствия с префиксом, а затем не возвращался при поиске в строке, так как для префиксного массива шаблона «abcdabca» будет {0, 0,0,0,1,2,3,1} Я понимаю до {0,0,0,0,1,2,3, _}, а затем 'd' на 4-й позиции не совпадает с 'a ' в конце концов. И тогда алго говорит вернуться к arr [j-1], если j! = 0, я вижу, что это дает нам правильный результат, но я не могу понять, почему мы возвращаемся к предыдущему элементу [data] для понимание основы.

Мы возвращаемся, пока не найдем подходящий элемент или j == 0, я не могу понять, почему мы возвращаемся.

Благодаря

Answer 1

В моем понимании, мы используем функцию отказа F[i] представлять в 0 на основе индекса самого длинного префикса, который является таким же, как суффикс подстроки S[0...i] (дольше всего, я имею в виду самый длинный кроме всего самого подстроки)

с вашей О.П., я думаю, что ваша реализация или учебник использует 1 на основе, но это полностью зависит от реализации

Рассмотрим следующий пример: S = abababcabab

Провал Функция будет как F = [-1,-1,0,1,2,3,-1,0,1,2,3]

Что вы можете посмотреть внимательно то, что происходит, когда алгоритм на время завершения расчета Failure функции для S' = ababab???? и F = [-1,-1,0,1,2,3,?,?,?,?,?]

Теперь следующий символ c, то алгоритм будет проверять, может ли он добавить на уже известный длинный префикс (суффикс) abab, чтобы сделать более длинным. Тест не работает как префикс ababa! = Суффикс ababc, но что тогда?

Тогда алгоритм будет пытаться выглядеть длинный префикс (суффикс) неисправного длинного префикса (суффикс) и посмотреть, что об ожидании c о том, что даст нам матч (если да, то ответ).

Это означает, что алгоритм будет проверять длинный префикс (суффикс) изabab которая ab, и мы знаем, что быстро, потому что мы знаем F(abab) = 3 (который мы тестируем для добавления c и терпит неудачу), и мы знаем F(F(abab)) = F(3) = 1, который является позицией ab.

То же самое происходит рекурсивно, пока, как вы сказали, мы не найдем совпадения или нет совпадения. «Перескакивание» F[] при неудачных совпадениях реализует этот процесс: протестируйте следующий потенциальный самый длинный префикс (суффикс), если не удается найти следующий ...