Blog. Just Blog

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

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

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

Единственным недостатком КМП-алгоритма можно отнести необходимость выделения памяти под таблицу префиксов-суффиксов максимальной длины, ну и предварительное заполнение этой таблицы. В остальном алгоритм крайне эффективен.
  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)


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

Комментарии

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

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

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

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0059 сек.) / Память: 4.5 Mb
Наверх