Прямий пошук стрічки

Нехай задано масив S з n елементів та масив P з m елементів, m<=n. Необхідно знайти перше входження масиву P у масив S. Алгоритм зводиться до повтору порівнянь окремих елементів.

Алгоритм R

R1. Встановити і=1.. n-m, j=1..m.

R2. Якщо S[i] = P[j], то зафіксувати перше співпадіння k=i, та перевірити співпадіння всього масиву P у масиві S. При першому неспівпадінні відмінити значення k та продовжити пошук.

R3. Кінець.

Кількість порівнянь дорівнює n*m.

Приклад.

Перша ітерація, співпав перший символ ‘a’=’a’:

a c a a b c

a a b

Друга ітерація, неспівпадіння ‘a’!=’c’:

a c a a b c

a a b

Третя ітерація, співпали всі символи масиву Р:

a c a a b c

A a b

Алгоритм Кнута, Моріса і Прата пошуку в стрічці.

Маємо масив символів S з n елементів (текст) та масив P з m - взірець. Необхідно знайти перше входження взірця в масив. Схема алгоритму полягає у поступовому порівнянні взірця з текстом та зсуву по тексту на кількість співпавших символів у разі знайденого неспівпадіння. Алгоритм використовує просте спостереження, що коли відбувається неспівпадіння тексту і взірця, то взірець містить у собі достатньо інформації для того, щоб визначити де наступне входження може початися, таким чином пропускаючи кількаразову перевірку попередньо порівняних символів. Попередньо проводиться дослідження взірця та визначається максимально можливий зсув взірця по тексту D_max. Для цього вираховується відстань між однаковими символами у взірці, якщо такі є, інакше D_max = m.

Алгоритм КМП

КМП 1. Встановити і=0.

КМП 2. j=0, d=1.

КМП 3. Поки j<m, i<n

Перевірка: якщо S[i]=P[j], то d++, i++.j++ поки d!= m.

КМП 4. Інакше встановити зсув взірця на d позицій по тексту якщо d <. D_max, або на D_max позицій якщо d > D_max. Перейти на крок КМП 2.

КМП 5. Кінець.

Складність алгоритму становить O(n+m).

Приклад.

abcabdabcabc – текст,

abcabc – взірець, m=6

D_max= 3