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

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


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

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

Вначале функция создает BMH-таблицу, содержимое которой зависит от искомого массива, а именно если число i не содержится в подмассиве W[1..m-1], то BMHTable[i]=m, если число i содержится в подмассиве W[1..m-1], то берется максимальный номер j, т.ч. W[j]=i и тогда BMHTable[i]=m-j. В дальнейшем таблица используется для "ускорения" прохода массива в котором осуществляется поиск, следующим образом:

   1. Положим j=m
   2. Пусть k=m; i=j. Пока W[k]=T[j] и k>0, уменьшаем на единицу k и i
   3. Если k=0, значит массив W входит в массив T начиная с номера i+1 и ВЫХОД.
   4. Увеличим значение j на BMHTable[T[j]] (действительно T[j] в массиве W может быть на расстоянии не меньшем, чем BMHTable[T[j]] от конца).
   5. Если j <= n переходим к шагу 2, иначе ВЫХОД и массив W не содержится в массиве T.

Алгоритм оптимизирован по сравнению с предыдущим для случая длинного искомого массива с не одинаковыми элементами. Интересно, что алгоритм работает намного медленее предыдущего например в случае когда массив T состоит из одних нулей, а массив W имеет следующий вид: 1000000.






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

 

 

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


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


 

 

 
 
На главную