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

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


Поиск подпоследовательности в массиве (алгоритм Кнута-Морриса-Пратта)

Поиск:
Функция осуществляет поиск первого вхождения массива W (размера m) в массив T, в результате функция выдает номер первого элемента в массиве T, начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Рассмотрим вначале функцию F, которая определена на последовательностях X[1], ..., X[k] следующим образом: рассмотрим все начала последовательности X одновременно являющиеся ее концами, и выберем из них самое длинное. (Не считая, конечно, самой последовательности X). Тогда F(X) равно длине такой подпоследовательности.

Работа алгоритма заключается в вычислении функции F на последовательности полученной слиянием массивов W и T с использованием разделителя, в качестве которого должен выступать элемент, не содержащийся ни в первом ни во втором массивах: W[1], ..., W[m], @, T[1], ..., T[j]; j = 1, ..., n. Тогда, если значение F при некотором j равно m (длине последовательности W), то массив W содержится в массиве T, иначе нет.

В первой части алгоритма заполняется массив L, при этом L[i] = F(W[1], ..., W[i]). На этом стоит остановится подробнее, т.к. методика заполнения массива L является ключевой в данном алгоритме. Итак тривиально L[1] = 0 (поскольку F - длина подпоследовательности). Далее, допустим мы заполнили массив L для элементов с первого по i-ый. Теперь необходимо определить значение L[i+1] = F(W[1], ..., W[i],W[i+1]). Для этого положим вначале len = L[i]. По построению массива L мы знаем, что W[i-len+1] = W[1], ..., W[i] = W[len], и если W[i+1] = W[len+1], то L[i+1] = L[i]+1, допустим это не так, т.е. W[i+1] не равно W[len+1], значит надо уменьшить длину начального подмассива который мы рассматриваем, положим len_ = L[len], тогда получаем W[i-len+1] = W[1] = W[len-len_+1] = W[i-len_+1], ..., W[i-len+len_] = W[len_] = W[len] = W[i], или выписав только важные для нас соотношения: W[1] = W[i-len_+1], ..., W[len_] = W[i], и осталось снова сравнить W[i+1] и W[len_+1], если они снова не равны положим len = len_; len_ = L[len], продолжая этот процесс мы на некотором шаге получим либо len = 0 и тогда L[i+1] = 0, если W[i+1]<>W[1] и L[i+1] = 1, если W[i+1] = W[1], либо равенство W[i+1] = W[len_+1] и значит L[i] = len_+1.

После заполнения массива L осуществляется вычисление функции F на массиве W[1], ..., W[m], @, T[1], ..., T[j]; j = 1, ..., n, воспользовавшись алгоритмом похожим на тот, что использовался в алгоритме Бойера - Мура - Хорспула, при этом разделитель как таковой не используется.






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

 

 

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


Популярные:
  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. Проверить дубляжи в столбце


 

 

 
 
На главную