Обработка цепочек элементов
Поиск с предварительным анализом искомой подстроки
Против незнания есть только одно средство – знание.
Истинное же знание может быть достигнуто только через личное совершенствование.
Л. Н. Толстой
Основу материала этого раздела составляет алгоритм КМП-поиска. Имя "КМП" является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца Р становится известной информация о просмотренной части. Работа алгоритма производится в два этапа.
- Анализируется строка-образец Р. По результатам анализа заполняется вспомогательный массив смещений D.
- Производится поиск в строке 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 на экран
Подробно, хотя и не очень удачно, алгоритм КМП-поиска описан у Вирта. Этот алгоритм достаточно сложен для понимания, хотя в конечном итоге его идея проста. Центральное место в алгоритме КМП-поиска играет вспомогательный массив D. Поясним его назначение. Массив D содержит значения, которые нужно добавить к текущему значению j в позиции первого несовпадения символов в строке S и подстроке Р (рис. 4.1).
Рис. 4.1. Пример КМП-поиска