Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (5)


Алгоритм Кнута-Морриса-Пратта

Поиск:
Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в конце подстроки (как префикс и как суффикс). Например, для подстроки abcHelloabc такой подстрокой является abc (одновременно и префиксом, и суффиксом). Смысл префикс-функции в том, что мы можем отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcHelloabc (следующий символ не совпал), то нам имеет смысл продолжать проверку продолжить поиск уже с четвертого символа (первые три и так совпадут). Вот как можно вычислить эту функцию для всех значений параметра от 1 до m:
Код


var S   : array[1..10000] of char;
    P  : array[1..10000] of word; {массив, в котором хранятся значения префикс-функции}
    i,k : longint;
    m  : longint;

Procedure Prefix; {процедура, вычисляющая префикс-функцию}
Begin
P[1]:=0; {префикс строки из одного символа имеет нулевую длину}
k:=0;
for i:=2 to m do {вычисляется для префиксов строки длинной от 2 до m символов}
begin
  while (k>0) and (S[k+1]<>S[i]) do
  k:=P[k]; {значение функции может быть получено из ранее сделанных вычислений}
  if S[k+1]=S[i] then
  k:=k+1;
  P[i]:=k; {присвоение префикс-функции}
end;
End;



Теперь разберемся, почему же данная процедура вычисляет префикс-функцию правильно. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]<k), но не становится меньше 0, то уменьшаться она может не чаще, чем возрастать. Переменная k возрастает на 1 не более m раз. Значит, переменная k меняется всего не более 2m раз. Выходит, что время работы всей процедуры есть O(m). А сейчас мы переходим к самой программе, ищущей строку в тексте.
Код

Program KnutMorrisPrattSearch;

{Описание процедуры Prefix и связанных с нею переменных}

var n : longint;
   T : array[1..40000] of char;
Begin
{Ввод текста и образца}

Prefix; {Вычисление префикс-функции}
k:=0; {количество символов, совпавших на данный момент}
for i:=1 to n do
begin
  while (k>0) and (S[k+1]<>T[i]) do
  k:=P[k];
  if S[k+1]=T[i] then
  k:=k+1;
  if k=m then {если совпали все символы}
  begin
   writeln('Образец входит в текст начиная с ',i-m+1,'-ого символа');
   k:=P[k];
  end;
end;
End.

Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

Напоследок хочу заметить, что простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считают, сколько символов совпало в процессе работы. И еще: алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее. Так что делайте выводы.

P.S. Все программы проверены на работоспособность, достаточно вставить соответствующие сегменты кода вместо многоточий.






Просмотров: 10985

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную