поиск строк по ключевым словам: вопросы о «сбойной функции»

Question

У меня есть вопрос об описании функции отказа из "Компиляторы: принципы, методы и инструменты", также называемые DragonBook

Во-первых, цитата:

Для быстрой обработки текстовых строк и поиска по ним по ключевому слову, Для ключевого слова b ₁ b ₂ ... b _n полезно определить позицию s в этом ключевом слове, функцию сбоя f (s) ) ... Цель состоит в том, что b ₁ b ₂ .. - b _{f (s)} - самый длинный правильный префикс b ₁ ... b _s , который также является суффиксом b ₁ ... b _s . Причина f (s) важна в том, что если мы пытаемся сопоставить текстовую строку для b _l b ₂ .. b _n , и мы сопоставили первые s позиции, но затем мы терпим неудачу (то есть следующая позиция текстовой строки делает не удерживать b _{s + l} ), тогда f (s) - самый длинный префикс b ₁ .. b _n , который может сопоставьте текстовую строку с той точкой, в которой мы находимся. Конечно, следующий персонаж текстовая строка должна быть b _{f (s) + 1} , иначе у нас все еще есть проблемы и мы должны рассмотреть еще более короткий префикс, который будет b _{f (f (s))} .

Итак, вопросы:
1. Если мы сопоставили s позиций с текстом, почему f (s) является самым длинным префиксом b ₁ .. b _n , который соответствует строка? Я думаю, s - это самый длинный префикс.
2. Следующий символ текстовой строки должен быть b _{f (s) + 1} , почему? У нас есть несоответствие в этой позиции, имеет ли значение вообще, что это за символ?

Answer 1

f (s) - самый длинный префикс в этой позиции, который может соответствовать всему ключевому слову. Идея состоит не в том, чтобы попытаться сопоставить ключевое слово с текстом с самого начала, а в том, чтобы найти позицию, где появляется ключевое слово.

Рассмотрим поиск слова «аааба» в тексте «аааабаа». Совпадение не удается после трех первых а, но нет необходимости повторять со второго «а», так как мы знаем, что если следующая буква - это «б» (то есть), у нас может быть совпадение.