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




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



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

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

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

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

Л. Н. Толстой

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

и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки 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 на экран




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