| Форма входа |
|
 |
| Меню сайта |
|
|
| Разное |
|
|
|
| Сейчас на сайте |
Онлайн всего: 7 Гостей: 7 Пользователей: 0 |
|
|
Алгоритм Кнута-Морриса-Пратта
|
| 18.09.2009, 03:59 |
Случайный текст с реферата
Алгоритм Кнута Морриса Пратта Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=x[1]x[2] x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1] l[n], где l[i]=длина слова l(x[1].х[i]) (функция l определена в предыдущем пункте) Словами: l[i] есть длина наибольшего начала слова x[1].x[i], одновременно являющегося его концом. Какое отношение все это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B? Решение Применим алгоритм КМП к слову A#B, где # специальная буква, не встречающаяся ни в A, ни в B Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. Описать алгоритм заполнения таблицы l[1].l[n]. Решение Предположим, что первые i значений l[1].l[i] уже найдены Мы читаем очередную букву слова (т.е x[i+1]) и должны вычислить l[i+1]. Другими словами, нас интересуют начала Z слова ...
|
| Категория: Программирование | Добавил: bestmms
(15.0 Kb)
|
| Просмотров: 346 | Загрузок: 38
| Рейтинг: 0.0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
