Алгоритм Кнута-Морріса-Пратта

Алгоритм Кнута-Морріса-Пратта заснований на принципі скінченного автомата, але він використовує більш простий метод обробки невідповідного символу. В цьому алгоритмі стани помічаються символами, збіг з якими повинен відбутися. Із кожного стану існує два переходи: один відповідає успішному порівнянню, інший – неспівпадінню. Успішне порівняння переводить нас в наступний вузол автомата, а у випадку неспівпадіння ми потрапляємо в попередній вузол, який відповідає зразку. Приклад автомата Кнута-Морріса-Пратта для підрядка наведено на рис. 2.

Рис. 2. Повний автомат Кнута-Морріса-Пратта для підрядка

При всякому переході по успішному порівнянню у скінченному автоматі Кнута-Морріса-Пратта відбувається вибірка нового символу із тексту. Переходи, які відповідають невдалому порівнянню, не призводять до вибірки нового символу; замість цього вони повторно використовують останній вибраний символ. Якщо ми перейшли в кінцевий стан, то це означає, що шуканий підрядок знайдений.

Повний алгоритм пошуку:

subLoc=l // вказівник поточного символу, що порівнюється, в підрядку

textLoc=l // вказівник поточного символу, що порівнюється, в тексті

while textLoc<=length(text) and subLoc<=length(substring) do

if subLoc=0 or text[textLoc]=substring[subLoc] then

textLoc=textLoc+l

subLoc=subLoc+l

else // збігу немає; перехід по неспівпадінню

subLoc=fail[subLoc]

end while

if (subLoc>length(substring) then

return textLoc-length(substring)+l // знайдений збіг

else

return 0 // шуканий підрядок не знайдений

end if

Розглянемо переходи по неспівпадінню. Якщо при збігу нічого особливого робити не потрібно: виконується перехід до наступного вузла, то переходи при неспівпадінню визначаються тим, як шуканий рядок співвідноситься сам із собою. Наприклад, при пошуку підрядка немає необхідності повертатися назад на чотири позиції при невиявленні символу . Якщо ми вже досягли п’ятого символу у зразку, то відомо, що перші чотири символи співпали і тому символи в тексті, які відповідають третьому і четвертому символам зразка, співпадають також з першим і другим символами зразка. Алгоритм, який задає ці співвідношення в підрядку:

fail[l]=0

for i=2 to length(substring) do

temp=fail[i-l]

while(temp>0) and substring[temp]=substring[i-1]) do

temp=fail[temp]

end while

fail[i]=temp+l

end for