Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Алгоритм Кнута-Морріса-Пратта
|
|
Алгоритм Кнута-Морріса-Пратта заснований на принципі скінченного автомата, але він використовує більш простий метод обробки невідповідного символу. В цьому алгоритмі стани помічаються символами, збіг з якими повинен відбутися. Із кожного стану існує два переходи: один відповідає успішному порівнянню, інший – неспівпадінню. Успішне порівняння переводить нас в наступний вузол автомата, а у випадку неспівпадіння ми потрапляємо в попередній вузол, який відповідає зразку. Приклад автомата Кнута-Морріса-Пратта для підрядка 
наведено на рис. 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
Date: 2015-12-11; view: 400; Нарушение авторских прав