Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
04.01.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21260.zip — 10.72 kb
  • algoritm-knuta-morrisa-pratta_21260_1.rtf — 52.81 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Алгоритм Кнута - Морриса - Пратта Цико Наталья Николаевна
Алгоритм Кнута - Морриса - Пратта
Реферат
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово
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], являющиеся одновременно его концами. Из них выберем подходящие - те,
за которыми идет буква x[i+1]. Из подходящих выберем самое длинное. Приписав



Ваше мнение



CAPTCHA