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

Против незнания есть только одно средство — знание.

Истинное же знание может быть достигнуто

только через личное совершенствование.

Л. Н. Толстой

Основу материала этого раздела составляет алгоритм КМП-поиска. Имя «КМП» является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса

и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца Р становится известной информация о просмотренной части. Работа алгоритма производится в два этапа.

1. Анализируется строка-образец Р. По результатам анализа заполняется вспомогательный массив смещений D.

2. Производится поиск в строке S с использованием строки-образца Р и массива смещений D.

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

//рrg4_73_КМР - программа на псевдоязыке поиска строки Р в строке S

//по алгоритму КМП-поиска. Длина S фиксирована. ..<. ¦ ¦¦ ¦¦

// Вход: S и Р - массивы символов размером N и М байт (M=<N)

II Выход: сообщение о количестве вхождений строки Р в строку S.

ПЕРЕМЕННЫЕ .

INT_BYTE s[n]://0=<i<N-l

INT_BYTE p[m]://0-<j<M-l .

INT_BYTE d[ml://массив смещений
INT_BYTE k=-l: i=0: j-0 //индексы

НАЧ_ПРОГ .

//этап 1: формирование массива смещений d

' И j:-0; k:-l:'d[0]

ПОКА ДЕЛАТЬ

НАЧ_БЛОК 1 .

nOKA~"((k>=0)M(p[j]<>p[k])) k:-d[k]

j:=j+l: k:-k+l :

ЕСЛИ p[j]-p[k] TO d[j]:-d[k] .

ИНАЧЕ d[j]:-k .

кон_блок_1 .

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

i:-0: j:-0: k:=0

ПОКА ((j<M)M(i<N)) ДЕЛАТЬ

НАЧ_БЛОК_1 ' '" '"'

ПОКА ((j>=O)H(s[i]<>p[j])) j:-dtj]

j:-j+l: i:=i+l

КОН_БЛОК_1

ЕСЛИ j=M TO зывод сообщения об удаче поиска
ИНАЧЕ вывод сообщения о неудаче поиска КОН ПРОГ

jmpm3

ml: :ЕСЛИ j=M TO вывод сообщения об удаче поиска :вывод сообщения о результатах поиска

cmp si ,len_p

jneexit_f :ИНАЧЕ вывод сообщения о неудаче поиска

inc count

cmp di ,len_s

jgeexit_f

xor si ,si

jmp m34

exit_f:add count.30h :вывод сообщения mes на экран

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