Реферат: Алгоритм Кнута - Морриса - Пратта

{нашли подходящее или убедились в отсутствии}

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] встанет такая же