КМП алгоритм

Рейтинг: 0Ответов: 0Опубликовано: 02.11.2014

Привет.

Это снова я, и я до сих пор не понял, как именно работает алгоритм Кнута-Морриса-Пратта. Ну никак.
Что я понял: что такое префикс-функция, а также то, что КМП использует префикс-функцию, выполненную для образца, чтобы ускорить поиск.
Что не понял: как выполненная префикс-функция для образца помогает увеличить скорость поиска. Например, строка и образец:

text = "aaaaazaaabcbaaaab"
pattern = "aaab"

prefix_function(pattern) = 0120

Теперь кто-нибудь сможет, не привязываясь к коду и к индексации (i, j), объяснить, как же КМП алгоритм использует "0120" для ускорения поиска.

Ответы

Ответов пока нет.