Алгоритм Кнута — Морриса — Пратта: различия между версиями

Рассмотрим сравнение строк на позиции <math>\displaystyle i</math>, где образец <math>\displaystyle S[ 0, m - 1 ]</math> сопоставляется с частью текста <math>\displaystyle \displaystyle T[ i, i + m - 1 ]</math>. Предположим, что первое несовпадение произошло между <math>\displaystyle T[ i + j ]</math> и <math>\displaystyle S[ j ]</math>, где <math>\displaystyle 1 < j < m</math>. Тогда <math>\displaystyle T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P</math> и <math>\displaystyle a = T[ i + j ] \ne S[ j ] = b</math>.

 

 

Это приводит нас к следующему алгоритму: пусть <math>\displaystyle \rm{\pi}[ j ]</math> — префикс-функция от строки <math>\displaystyle S[ 0, j - 1 ]</math>. Тогда после сдвига мы можем возобновить сравнения с места <math>\displaystyle T[ i + j ]</math> и <math>\displaystyle S[ \rm{\pi}[ j ] ]</math> без потери возможного местонахождения образца. Средствами амортизационного анализа можно показать, что таблица <math>\displaystyle \rm{\pi}</math> может быть вычислена за <math>\displaystyle \Theta( m )</math> сравнений перед началом поиска. А поскольку строка <math>\displaystyle T</math> будет пройдена ровно один раз, суммарное время работы алгоритма будет равно <math>\displaystyle \Theta(m + n)</math>, где <math>n</math> - длина текста <math>\displaystyle T</math>.