Алгоритм Кнута — Морриса — Пратта
Алгоритм Кнута-Морриса-Пратта (КМП) получает на  вход слово
         X=x[1]x[2]… x[n]
и просматривает его слева направо буква за буквой, заполняя при этом массив
натуральных чисел l[1]… l[n], где
         l[i]=длина слова l(x[1]…х[i])
(функция l определена в предыдущем пункте). Словами: l[i] есть длина
наибольшего начала слова x[1]…x[i], одновременно являющегося его концом.
    Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения того,
является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # — специальная буква, не
встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и
только тогда, когда среди чисел в массиве l будет число, равное длине слова
A.
    Описать алгоритм заполнения таблицы l[1]…l[n].
Решение. Предположим, что первые i значений l[1]…l[i] уже найдены. Мы
читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1].
[pic]
Другими словами, нас интересуют начала Z слова
         x[1]…x[i+1,
одновременно являющиеся его концами -из них нам надо брать самое длинное.
Откуда берутся эти начала? Каждое из них (не считая пустого) получается из
некоторого слова Z' приписыванием буквы x[i+1] . Слово Z' является началом
и
концом слова x[1]…x[i]. Однако не любое слово, являющееся началом и
концом слова x[1]…x[i], годится — надо, чтобы за ним следовала буква
x[i+1].
     Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова
x[1]…x[i], являющиеся одновременно его концами. Из них выберем подходящие
— те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное.
Приписав в его конец х[i+1], получим искомое слово Z. Теперь пора
воспользоваться сделанными нами приготовлениями и вспомнить, что все слова,
являющиеся одновременно началами и концами данного слова, можно получить
повторными применениями к нему функции l из предыдущего раздела.
    Вот что получается:
         i:=1; 1[1]:=0;
    {таблица l[1]..l[i] заполнена правильно}
    while i <> n do begin
       len:= l[i]
       {len — длина начала слова x[1]..x[i], которое является
       его концом; все более длинные начала оказались
       неподходящими}
       while (x[len+1]<>х[i+1]) and (len>0) do begin
           {начало не подходит, применяем к нему функцию l}
         len:=l[len];
         end;
           {нашли подходящее или убедились в отсутствии}
         if x[len+1]=x[i+1] do begin
           {х[1]..x[len] — самое длинное подходящее начало}
         l[i+1]:=len+1;
         end else begin
           {подходящих нет}
         l[i+1]:= 0;
       end;
       i:=i+1;
    end;
       Доказать, что число действий в приведенном только что алгоритме не
превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы может
потребовать многих итераций во внутреннем цикле. Однако каждая такая
итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1]
окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу
величина l[i] может возрасти не более чем на 1, так что часто и сильно
убывать она не может — иначе убывание не будет скомпенсировано
возрастанием.
     Более точно, можно записать неравенство
        l[i+1]<l [i] — (число итераций на i-м шаге)+1
или
       (число итераций на i-м шаге)<= l[i]-l[i+1]+1
Остается сложить эти неравенства по всем i и получить оценку
сверху для общего числа итераций.
       Будем использовать этот алгоритм, чтобы выяснить, является ли слово
X длины n подсловом слова Y длины m. (Как это делать с помощью специального
разделителя #, описано выше.) При этом число действий будет не более
C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не
более Cn (что может быть существенно меньше, если искомый образец короткий,
а слово, в котором его ищут — длинное).
Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений
l[1],…,l [n] проводим для слова X длины n и запоминаем эти значения.
Дальше мы помним только значение l[i] для текущего i — кроме него и кроме
таблицы
l[1]…l[n], нам для вычислений ничего не нужно.
     На практике слова X и Y могут не находиться подряд, поэтому просмотр
слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет
также от хлопот с разделителем.
     Написать соответствующий алгоритм (проверяющий, является ли слово
X=x[1]…x[n] подсловом слова Y=y[1]…y[m]
Решение. Сначала вычисляем таблицу l[1]…l[n]как раньше. Затем пишем такую
программу:
    j:=0; len:=0;
        {len — длина максимального качала слова X, одновременно
                   являющегося концом слова y[1]..j[j]}
    while (len<>n) and (j<>m) do begin
         while (x[len+1]<>у[j+1]) and (len>0) do begin
                {начало не подходит, применяем к нему функцию l}
             len: = l[len];
             end;
                {нашли подходящее или убедились в отсутствии}
             if x[len+1]=y[j+1] do begin
                {x[1]..x[len] — самое длинное подходящее начало}
             len:=len+1;
             end else begin
                {подходящих нет}
             len:=0;
         end;
         j:=j+1;
    end;
    {если len=n, слово X встретилось; иначе мы дошли до конца
    слова Y, так и не встретив X}
Алгоритм Бойера — Мура
   Этот алгоритм делает то, что на первый взгляд кажется невозможным: в
типичной ситуации он читает лишь небольшую часть всех букв слова, в котором
ищется заданный образец. Как так может быть? Идея проста. Пусть, например,
мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру,
это буква e, то нет никакой необходимости читать первые три буквы. (В самом
деле, в образце буквы e нет, поэтому он может начаться не раньше пятой
буквы.)
   Мы приведем самый простой вариант этого алгоритма, который не
гарантирует быстрой работы во всех случаях. Пусть x[1]…х[n] — образец,
который надо искать. Для каждого символа s найдем самое правое его
вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения
будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам
будет удобно положить pos[s]=0 (мы увидим дальше, почему).
  Как заполнить массив pos?
Решение.
положить все pos[s] равными 0
         for i:=1 to n do begin
             pos[x[i]]:=i;
         end;
В процессе поиска мы будем хранить в переменной last номер буквы в слове,
против которой стоит последняя буква образца. Вначале last=n (длина
образца), затем last постепенно увеличивается.
         last:=n;
         {все предыдущие положения образца уже проверены}
         while last<= m do begin {слово не кончилось}
               if x[m]<>y[last] then begin {последние буквы разные}
                  last:=last+(n-pos[y[last]]);
                 {n — pos[y[last]] — это минимальный сдвиг образца,
                        при котором напротив y[last] встанет такая же
                        буква в образце. Если такой буквы нет вообще,
                        то сдвигаем на всю длину образца}
               end else begin
              если нынешнее положение подходит, т.е. если
                     x[i]..х[n]=y[last-n+1]..y[last],
                     то сообщить о совпадении;
                     last:=last+1;
               end;
         end;
Знатоки рекомендуют проверку совпадения проводить справа налево, т.е.
начиная с последней буквы образца (в которой совпадение заведомо есть).
Можно также немного сэкономить, произведя вычитание заранее и храня не
pos[s], а n-pos[s],
т.е. число букв в образце справа от последнего вхождения буквы Возможны
разные модификации этого алгоритма. Например, можно строку
         last:=last+i
заменить на
         last:=last+(n-u),
где u — координата второго справа вхождения буквы x[n] в образец.
Как проще всего учесть это в программе
Решение. При построении таблицы pos написать
         for i:=1 to n-1 do…
(далее как раньше), а в основной программе вместо
         last:=last+1
написать
         last:=last+n-pos[y[last]];
Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях
требует существенно больше n действий (число действий порядка mn),
проигрывая алгоритму Кнута-Морриса-Пратта.
 Пример ситуации, в которой образец не входит в слово, но алгоритму
требуется порядка mn действий, чтобы это установить.
Решение. Пусть образец имеет вид baaa… aa, а само слово состоит только из
букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний
момент.
Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число
действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие
к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали
образец со входным словом, идя справа налево. При этом некоторый кусок Z
(являющийся концом образца) совпал, а затем обнаружилось различие: перед Z
в образце стоит не то, что во входном слове. Что можно сказать в этот
момент о
входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та
буква, что в образце. Эта информация может позволить сдвинуть образец на
несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги
следует вычислить заранее для каждого конца Z нашего образца. Как говорят
знатоки, все это (вычисление таблицы сдвигов и ее использование) можно
уложить в C(m+ n) действий.
Алгоритм Рабина
    Этот алгоритм основан на простой идее. Представим себе, что в слове
длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать
его по входному слову. Нас интересует, не совпадает ли слово в окошечке с
заданным
образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую
функцию, определенную на словах длины n. Если значения этой функции на
слове в окошечке и на образце различны, то совпадения нет. Только если
значения одинаковы, нужно проверять совпадение по буквам.
      В чем выигрыш при таком подходе. Казалось бы, ничего — ведь чтобы
вычислить значение функции на слове в окошечке, все равно нужно прочесть
все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не
менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не
меняется полностью, а лишь добавляется буква в конце и убирается в начале.
Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется
функция.
   Привести пример удобной для вычисления функции.
Решение. Заменим все буквы в слове и образце их номерами, представляющими
собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге
окошечка нужно добавить новое число и вычесть пропавшее.)
     Для каждой функции существуют слова, к которым она применима плохо.
Зато другая функция в этом случае может работать хорошо. Возникает идея:
надо запасти много функций и в начале работы алгоритма выбирать из них
случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет
знать, с какой именно функцией ему бороться.)
 Привести пример семейства удобных функций.
Решение. Выберем некоторое число p (желательно простое, смотри далее) и
некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как
последовательность целых чисел (заменив буквы кодами). Эти числа будем
рассматривать как коэффициенты многочлена степени n-1 и вычислим значение
этого многочлена по модулю p в точке x. Это и будет одна из функций
семейства (для каждой пары p и x получается, таким образом, своя функция).
Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует
вычислить заранее), умножению на x и добавлению свободного члена.
       Следующее соображение говорит в пользу того, что совпадения не
слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y —
два различных слова длины n. Тогда им соответствуют различные многочлены
(мы предполагаем, что коды всех букв различны — это возможно, если p больше
числа букв алфавита). Совпадение значений функции означает, что в точке x
эти два различных многочлена совпадают, то есть их разность обращается в 0.
Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким
образом, если и много меньше p, то случайному x мало шансов попасть в
неудачную точку.