Сборник по задачам и примерам Assembler




Поиск с предварительным анализом искомой подстроки - часть 2


Подробно, хотя и не очень удачно, алгоритм КМП-поиска описан у Вирта [4]. Этот алгоритм достаточно сложен для понимания, хотя в конечном итоге его идея проста. Центральное место в алгоритме КМП-поиска играет вспомогательный массив D. Поясним его назначение. Массив D содержит значения, которые нужно добавить к текущему значению j в позиции первого несовпадения символов в строке S и подстроке Р (Рисунок 4.1).

Рис 4.1. Пример КМП-поиска

Из обсуждения выше можно сделать два вывода — один приятный, другой не очень. Во-первых, явное достоинство этого метода в том, что исключены возвраты

:задаем массив S

s db "fgcabceabcaab"

Len_S=$-s :N=Len_S

db Count db 0 ;счетчик вхождений Р в S

Db " раз(а)$"

d db 255 dup (0) вспомогательный массив ¦' ¦ k db 0 .,.,.,'

.code

:этап 1 - заполнение массива D значением М - размером образца для поиска

mov ex.255 :размер кодовой таблицы ASCII

moval.lenjj :ДЛЯ j=0 ДО 255 ДЕЛАТЬ

lea di .d rep stosb :d[j]:=M

:цикл просмотра образца и замещение некоторых элементов d значениями смещений :(см. пояснение за текстом программы)

xor si .si ; j:=0 '

cycll: :ДЛЯ j>0 ДО М-2 ДЕЛАТЬ ..>;

empsi ,1еп_р-1

jgee_cycll

mov al ,p[si]

movdi.ax

movbl.len_p

decbl

subbx.si

movd[di],bl :d[p[j]]:-MrJ-l:!

inc si ¦, -.r

e_cycll: ://этап 2: поиск

movdi,len_p

cycl 2:,; ПОВТОРИТЬ - цикл пока (j>-0)WW(I<n) . movsi.len_p :j:=M . , ;¦

movbx.di :k:=I . '.

cycl3: :цикл пока (j>-O)MJlH(p[j]~p[k])

decbx :k:-k-l . ' '¦' '

dec si :j:-j-l cmp si.0 jl m2

mov al.p[si] cmps[bx].al jnem2 jmpcycl3 m2: ;i:-i+d[s[i-: push di dec di

mov al,s[di] mov di ,ax moval .dfdi] popdi

add di .ax cmp s i, 0 jl ml cmp di .len_s

jg exi t_f

jmp cycl2 ml: ;вывод сообщения о результатах поиска

inc count

jmpcycl2 exit_f:add count.30h

lea dx.mes

mov ah.09h

int 21h exit:

Идея алгоритма БМ-поиска в том, что сравнению подвергаются не первые, а последние символы образца Р и очередного фрагмента строки S. Если они не равны, то сдвиг в строке S осуществляется сразу на всю длину образца. Если последние символы равны, то сравнению подвергаются предпоследние символы, и т. д. При несовпадении очередных символов величина сдвига извлекается из таблицы D, которая, таким образом, выполняет ключевую роль в этом алгоритме. Заполнение таблицы происходит на основе конкретной строки-образца Р следующим образом. Размер таблицы определяется размером алфавита, то есть количеством кодов символов, которые могут появляться в тексте. В нашем случае мы отвели под таблицу D память длиной, равной длине кодовой таблицы ASCII. Таким образом, строки S и Р могут содержать любые символы. Первоначально все байты кодовой таблицы заполняются значением, равным длине строки-образца для поиска Р. Далее последовательно извлекаются символы строки-образца Р начиная с первого. Для каждого символа определяется позиция его самого правого вхождения в строку-образец Р. Это значение и заносится в таблицу D на место, соответствующее этому символу. Подробнее получить представление о заполнении таблицы можно по фрагменту программы на псевдоязыке:




Содержание  Назад  Вперед