Какой алгоритм сопоставления с образцом это?

Question

Я читал книгу «Теория и проблемы структуры данных» (Сеймур Липшуз).

Позвольте мне представить изображение раздела, который я читал. .

Этот разделВ книге рассказывается об алгоритме сопоставления с образцом под названием «Второй алгоритм сопоставления скороговорок».

Что это за алгоритм?Это Бойер-Мур, или КМП, или Хоршпул, или как?

Или это какой-то новый алгоритм, созданный автором?

Answer 1

Я считаю, что это алгоритм KMP . KMP создает «таблицу ошибок», которая, по сути, является автоматом, говорящим «если вы не соответствуете определенному символу, какую часть строки шаблона вы все еще можете сопоставить? Он также выполняет предварительную обработку шаблона, а не сопоставляемой строки. Более того, если вы посмотрите на алгоритм Aho-Corasick, который является обобщением KMP, он построит более общую версию этого автомата, которая работает с несколькими шаблонами одновременно. Следовательно, я почти уверен, что вы смотрите на KMP.