2015-10-13
559
Нажаль співпадіння зустрічаються значно рідше, ніж неспівпадіння. Тому виграш від використання алгоритму КМП в більшості випадків незначний. Іншийалгоритму Бойера-Мура базується на наступній схемі: порівняння символів починається з кінця взірця, а не з початку. Нехай для кожного символу x взірця dx - відстань від самого правого у взірці входження х до кінця взірця. Припустимо, знайдено неспівпадіння між взірцем та текстом. Тоді взірець можна зразу посунути вправо на dx позицій що є більше або рівне 1. Якщо х у взірці взагалі не зустрічається, то посунути взірець можна зразу на всю його довжину m.
В даному алгоритмі розглядається поняття стоп-символа - це є символ в тексті, який є першим неспівпадінням тексту і взірця при порівнянні справа (з кінця взірця). Розглянемо три можливих ситуації:
1. 1. Стоп-символ у взірці взагалі не зустрічається, тоді зсув дорівнює довжині взірця m.
2. 2. Крайня права позиція k входження стоп-символа у взірці є меншою від його позиції j у тексті. Тоді взірець можна зсунути вправо на k-j позицій так, щоб стоп-символ у взірці і тексті опинились один під одним.
|
|
|
3. 3. Крайня права позиція k входження стоп-символа у взірці є більшою від його позиції j у тексті. Такий зсув ігнорується.
У третій ситуації необхідно знайти співпадіння взірця і тексту. Якщо у взірці є ще один такий самий символ, то необхідно зсунути взірець до співпадіння цього символу з символом в тексті. Інакше зсув дорівнює 1.
Приклад [4].
Hoola-Hoola girls like Hooligan - текст,
Hooligan - взірець.
Перша ітерація:
Hoola-Hoola girls like Hooligan
Hooliga n
‘n’!=’o’, символ ‘ о’ у взірці стоїть на 6-й позиції з кінця. Зсуваємо взірець на 6-1=5 позицій вправо.
Друга ітерація:
Hoola-Hoola girls like Hooligan
Hooliga n
‘n’!=’g’, символ ‘ g’ стоїть на 3-й позиції з кінця. Зсуваємо взірець на 3-1=2 позиції вправо
Третя ітерація:
Hoola-Hoola girls like Hooligan
Hooliga n
‘n’!=’r’, символа ‘r’ у взірці взагалі немає. Зсуваємо взірець на всю довжину, тоб то на 8-1=7 позицій.
Четверта ітерація:
Hoola-Hoola girls like Hooligan
Hooliga n
‘n’!=‘e‘, символа ‘e‘ у взірці взагалі немає. Зсуваємо взірець на всю довжину, тоб то 8-1=7 позицій.
Hoola-Hoola girls like Hooligan
Hooliga n
‘n’!=’g’, символ ‘ g’ стоїть на 3-й позиції з кінця. Зсуваємо взірець на 3-1=2 позиції вправо
Hoola-Hoola girls like Hooligan
Hooligan
Всі символи співпали. Входження знайдено.
В найгіршому випадку алгоритм потребує n порівнянь, n - кількість символів у тексті. У найкращих обставинах, коли останній символ взірця завжди не співпадає з символом тексту, число порівнянь дорівнює n / m, m - кількість символів взірця.
