Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail 11.06.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта
Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.

Единственным недостатком КМП-алгоритма можно отнести необходимость выделения памяти под таблицу префиксов-суффиксов максимальной длины, ну и предварительное заполнение этой таблицы. В остальном алгоритм крайне эффективен.
Code (Assembler) : Убрать нумерацию
  1. ;----------------------------------------------------------------------
  2. ; Функция поиска подстроки в строке по алгоритму Кнута-Морриса-Пратта
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpHaystack - указатель на исходную строку
  7. ;   dHLen - длина исходной строки
  8. ;   lpNeedle - указатель на строку для поиска
  9. ;   dNLen - длина строки для поиска
  10. ; На выходе:
  11. ;   EAX = позиция подстроки в строке
  12. ;   EAX = -1 если подстрока не найдена
  13. ;----------------------------------------------------------------------
  14. proc kmp_search lpHaystack:DWORD,dHLen:DWORD,lpNeedle:DWORD,dNLen:DWORD
  15.         locals
  16.                 hMem dd ?
  17.         endl
  18.  
  19.         pusha
  20.  
  21.         ; Искомая строка длиннее области поиска?
  22.         mov     eax,[dHLen]
  23.         cmp     eax,[dNLen]
  24.         jb      .loc_error
  25.  
  26.         ; Строки не могут быть пустыми
  27.         cmp     [dHLen],0
  28.         je      .loc_error
  29.         cmp     [dNLen],0
  30.         je      .loc_error
  31.  
  32.         ; Выделить память под массив префиксов-суффиксов
  33.         mov     eax,[dNLen]
  34.         shl     eax,2
  35.         invoke  GlobalAlloc,GMEM_MOVEABLE+GMEM_ZEROINIT,eax
  36.         mov     [hMem],eax
  37.         invoke  GlobalLock,[hMem]
  38.         mov     ebx,eax
  39.  
  40.         mov     edx,[lpNeedle]
  41.         xor     edi,edi
  42.         mov     [ebx],edi
  43.         mov     esi,1
  44. .loc_pre:
  45.         cmp     esi,[dNLen]
  46.         jae     .loc_pre_done
  47.  
  48.         mov     al,byte[edx+esi]
  49.         cmp     al,byte[edx+edi]
  50.         jne     @f
  51.  
  52.         inc     edi
  53.         mov     dword[ebx+esi*4],edi
  54.         inc     esi
  55.         jmp     .loc_pre
  56. @@:
  57.         cmp     edi,0
  58.         jne     @f
  59.  
  60.         mov     dword[ebx+esi*4],0
  61.         inc     esi
  62.         jmp     .loc_pre
  63. @@:
  64.         mov     edi,dword[ebx+edi*4-4]
  65.         jmp     .loc_pre
  66. .loc_pre_done:
  67.  
  68.         xor     esi,esi
  69.         xor     edi,edi
  70. .loc_search:
  71.         cmp     esi,[dHLen]
  72.         jae     .loc_search_done
  73.  
  74.         mov     edx,[lpHaystack]
  75.         mov     al,byte[edx+esi]
  76.         mov     edx,[lpNeedle]
  77.         cmp     al,byte[edx+edi]
  78.         jne     @f
  79.  
  80.         inc     esi
  81.         inc     edi
  82. @@:
  83.         cmp     edi,[dNLen]
  84.         jne     @f
  85.  
  86.         mov     ebx,esi
  87.         sub     ebx,[dNLen]
  88.         jmp     .loc_clear
  89. @@:
  90.         cmp     esi,[dHLen]
  91.         jae     .loc_search
  92.         mov     edx,[lpHaystack]
  93.         mov     al,byte[edx+esi]
  94.         mov     edx,[lpNeedle]
  95.         cmp     al,byte[edx+edi]
  96.         je      .loc_search
  97.  
  98.         cmp     edi,0
  99.         jne     @f
  100.         inc     esi
  101.         jmp     .loc_search
  102. @@:
  103.         mov     edi,dword[ebx+edi*4-4]
  104.         jmp     .loc_search
  105.  
  106. .loc_search_done:
  107.         ; Подстрока не найдена
  108.         mov     ebx,-1
  109. .loc_clear:
  110.         ; Прибраться за собой
  111.         invoke  GlobalUnlock,[hMem]
  112.         jmp     .loc_done
  113. .loc_error:
  114.         ; Подстрока не может быть найдена
  115.         mov     ebx,-1
  116. .loc_done:
  117.         ; Результат в EAX
  118.         mov     [esp+28],ebx
  119.         popa
  120.         ret
  121. endp
Функции передается четыре параметра: указатель на исходную строку, длина исходной строки, указатель на строку для поиска и длина строки для поиска. Если подстрока была найдена, то в регистре EAX вернется ее позиция в строке, иначе EAX будет равно -1. Никаких ограничений на длину обрабатываемых данных нет, кроме размерности DWORD.

В приложении пример программы с исходным текстом, которая ищет подстроку в строке по алгоритму Кнута-Морриса-Пратта.

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

Knuth.Morris.Pratt.Search.Demo.zip (2,413 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 427 | Комментариев: 1

Комментарии

Отзывы посетителей сайта о статье
user (15.06.2024 в 08:13):
У меня при парсинге больших файлов профайлер показывает проседание именно на простой функции поиска подстроки (либа самописная). Так что да, это достаточно важная оптимизация.

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (30), AJAX (5), Assembler (362), COM (41), CSS (42), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (52), iconBIT (4), JavaScript (73), MySQL (13), Nikon (19), PDF (10), PHP (122), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (66), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (19), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (125), выпечка (29), выставки (119), генератор ПСЧ (10), графика (120), десерты (31), Египет (8), заготовки на зиму (47), закуска (22), закуска к пиву (25), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (317), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (69), мониторы (6), музеи (78), мультимедиа (77), мясо (62), напитки (14), ноутбуки (8), обфускация (7), окна (69), оформление сайта (50), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (130), полезные функции (42), прохождения (4), процессы (25), птица (21), путешествия (25), распаковка (22), реверсинг (52), рыба (35), салаты (19), сброс триала (4), сеть (36), система (178), Сокольники (8), соусы (14), супы (14), телефоны (10), Тунис (6), умный дом (13), файлы справки (6), фаст-фуд (18), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 35,328 раз
<< 2024 - ОКТЯБРЬ >>
Пн Вт Ср Чт Пт Сб Вс
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
День кадрового работника
Всемирный день борьбы с артритом
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 2 (0.0032 сек.) / Память: 4.5 Mb
Наверх