Поиск с предварительным анализом искомой подстроки
Поиск с предварительным анализом искомой подстроки
Против незнания есть только одно средство — знание.
Истинное же знание может быть достигнуто
только через личное совершенствование.
Л. Н. Толстой
Основу материала этого раздела составляет алгоритм КМП-поиска. Имя «КМП» является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса
и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца Р становится известной информация о просмотренной части. Работа алгоритма производится в два этапа.
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 на экран