КМП алгоритм
Привет.
Это снова я, и я до сих пор не понял, как именно работает алгоритм Кнута-Морриса-Пратта. Ну никак.
Что я понял: что такое префикс-функция, а также то, что КМП использует префикс-функцию, выполненную для образца, чтобы ускорить поиск.
Что не понял: как выполненная префикс-функция для образца помогает увеличить скорость поиска. Например, строка и образец:
text = "aaaaazaaabcbaaaab"
pattern = "aaab"
prefix_function(pattern) = 0120
Теперь кто-нибудь сможет, не привязываясь к коду и к индексации (i, j), объяснить, как же КМП алгоритм использует "0120" для ускорения поиска.
Источник: Stack Overflow на русском