Категория
Информатика
Тип
реферат
Страницы
3 стр.
Дата
03.05.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
108457.zip — 19.59 kb
  • algoritmy-v-programmirovanii_108457_1.rtf — 128.64 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

АА;
Алгоритм Кнута - Морриса - Пратта
Буель Анатолий Владимирович
9
Алгоритм Кнута-Морриса-Прат та
Алгоритм Кнута-Морриса-Пратта (КМП ) получает
на вход слово X=x[1]x[2]... x[n]
и просматривает его
слева направо буква за буквой , заполняя при этом массив натуральных чисел l[1]... l[n], где
l[i]=длина слова
l(x[1]...х [i]) (функция
l определена в предыд ущем пункте ). Словами : l[i] есть длина наибольшего начала слова
x[1][i], одновременно являющегося его концом.
Какое отношение все это имеет к поиску подслова ?
Другими словами , как использовать алгоритм КМП для определения того , является ли
слово A подс ловом слова B?
Решение . Применим алгоритм КМП к слову A#B, где # - специальная буква , не
встречающаяся ни в A, ни в B. Слово A является
подсловом слова B тогда и только тогда
, когда среди чисел в массиве l будет число , равное длине слова A.
Описать алгорит м заполнения таблицы l[1][n].
Решение . Предположим , что первые i значений
l[1][i] уже найдены . Мы читаем очередную букву
слова (т.е . x[i+1]) и должны вычислить l[i+1].
Другими с ловами , нас
интересуют начала Z слова
x[1][i+1,
одновременно являющиеся его концами -из них
нам надо брать самое длинное . Откуда берутся эти начала ? Каждое из них (не считая пустого ) получается из некоторого слова
Z' приписыванием буквы x[i+1] . Слово Z' является
началом и концом
слова x[1][i]. Однако не любое слово , являющееся началом и концом слова x[1][i], годится - надо , чтобы за ним следовала буква x[i+1].
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова
x[1][i],



Ваше мнение



CAPTCHA