A b a c a b a b

A b a c a b a a b a b a b a c a b a b b

0 0 1 0 1 2 3 2

A b a c a b a b

Ниже представлена последовательность сдвигов. Слева показана разность j - f(j), определяющая величину сдвига, а справа – позиция образца, с которой будет продолжено последующее сравнение с текстом

7-3=4 a b a c a b a b позиция 4

3-1=2 a b a c a b a b позиция 2

1-0=1 a b a c a b a b позиция 1

3-1=2 a b a c a b a b позиция 2

3-1=2 a b a c a b a b позиция 2

Представим образец массивом символов P, функцию возвратов целочисленным массивом F и опишем ее вычисления в следующем фрагменте программы:

k:=0;

F[1]:=0;

For i:=2 to M do

begin

While (k>0) and (P[i]<>P[k+1]) do k:=F[k];

if P[i]=P[k+1] then k:=k+1;

F[i]:=k;

end;

Обозначим через w (i) количество выполнений тела цикла While при i = 2, 3,…, M. Каждое выполнений тела цикла While уменьшает значение k не меньше, чем на 1. Отсюда

F[i] ≤ F[i-1] – w (i) +1, то есть w ( i ) ≤ F[i-1] – F[i] + 1

Тогда после суммирования w (2) + w (3) +…+ w (M) ≤ M – 1. Общая трудоемкость построения функции возвратов составляет O(M).

Поиск подстроки можно реализовать следующей программой. В ней опущены некоторые технические детали, связанные с вводом и выводом данных.

Program SubString;

Var

P: array[1..255] of char;

F: array[1..255] of integer;

C: char; {очередной символ текста}

pp: integer; {текущая позиция в образце}

tp: integer; {текущая позиция в тексте}

Fin, Fout: text; {входной и выходной файлы}

Begin

{ввод образца, построение массива F:

значений функции возвратов}

pp:=0;

tp:=0;

While not eof(Fin) do

Begin

tp:=tp+1;

Read(Fin,C); {очередной символ текста}

While (pp>0) and (P[pp+1]<>C) do

pp:=F[pp]; {следующее ‘начало-конец’}

if P[pp+1]=C then pp:=pp+1;

if pp = M then {совпал последний символ образца}

begin

Write(Fout,tp-M+1,' ');

{позиция первого символа}

pp:=F[pp];

{подготовка к поиску следующего вхождения}

end;

End;

End.

Оценим количество сравнений символов. На каждом шаге внешнего цикла tp увеличивается на 1, а pp увеличивается на 1, а иногда уменьшается как минимум на 1 за счет присваивания F[pp]. Обозначим через b (tp) начальное значение pp при очередном значении tp, а через w (tp) – количество уменьшений pp при одной и той же позиции tp в тексте. Тогда b (tp) ≤ b (tp -1) – w (tp)+1 при tp >1 или w (tp) ≤ b (tp -1) - b (tp)+1. Отсюда вычисление суммы значений w (i) имеет трудоемкость порядка N. Поскольку tp увеличивается N -1 раз, то общая трудоемкость алгоритма с учетом вычисления функции возвратов составляет O (M+N).

Алгоритм КМП обеспечивает во всех случаях линейную сложность, но не является самым эффективным алгоритмом.

Алгоритм Бойера – Мура [19] имеет нелинейную оценку трудоемкости в худшем случае, но в среднем работает быстрее. Здесь можно провести аналогию с широко известным алгоритмом быстрой сортировки Хоара [1, 3, 5, 7, 11], который имеет квадратичную трудоемкость на специально подобранных данных. Этот алгоритм считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее мы совмещаем начала строки и образца и начинаем проверку с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. При несовпадении очередного символа величина сдвига определяется выражением L - K, где L – значение из таблицы смещений, а K – количество совпавших символов. После сдвига снова начинаем проверку с последнего символа.

Если все символы образца совпали с наложенными символами строки, значит, мы нашли подстроку. Если одной подстроки достаточно, то поиск окончен. Иначе сдвигаем образец либо на его длину в том случае, когда находимые подстроки не должны пересекаться, либо на один символ.

Величина сдвига в случае несовпадения символа вычисляется, исходя из следующих соображений: сдвиг образца должен быть минимальным, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, мы смещаем образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце.

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Если символ отсутствует в образце, то заносится значение M.

Поясним все вышесказанное на простом примере. Пусть у нас есть алфавит из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца abaad в строке abecdacbbdbabaad. Длина образца M = 5. Таблица смещений будет выглядеть так:

Дата добавления: 2014-01-11