Поиск с предварительным анализом искомой подстроки - часть 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 на место, соответствующее этому символу. Подробнее получить представление о заполнении таблицы можно по фрагменту программы на псевдоязыке: