2. Задача поиска в строке

   1. Постановка задачи и «прямое» решение

В данном подразделе будет рассмотрена задача, существенно отличающаяся от задач поиска в таблицах, которым была посвящена большая часть предыдущего материала. Объединяющим здесь является само понятие поиска.

Задача поиска подстроки в строкеставится следующим образом. Дана строкаA, состоящая изnсимволов (строка поиска) и строкаSизmсимволов (искомая подстрока-образец). Требуется определить, содержится ли образецSв строке поискаA. При положительном ответе надо вернуть номер позицииA, с которой начинается первое вхождениеS, а в противном случае надо вернуть 0.

По сути дела, это именно та задача, которая выполняется по команде поиска в текстовых редакторах.

Мы не будем здесь использовать готовый строковый тип данных Паскаля или C, и тем более применять строковые функции, определенные для этих типов. Наша задача как раз в том, чтобы разобраться в работе функции поиска в строке. Будем рассматривать строки просто как массивы символов.

Очевидное «прямое» решение задачи состоит в том, чтобы посимвольно сравнивать массивы AиS, а в случае несравнения очередной пары символов сдвигатьSна одну позицию вдольAи начинать цикл сравнения заново. Ниже приведены описания соответствующих типов данных и определение функции поиска.

const

N = ... ; {Длина строки поиска}

M = ... ; {Длина подстроки-образца}

type

StringN = array[1..N] of Char;

StringM = array[1..M] of Char;

function StraightSearch(A: StringN; S: StringM): Integer;

var

i, j: Integer;

begin

i := -1;

repeat

i := i + 1; {Сдвиг на одну позицию по A}

j := 1;

while (j <= M) and (A[i+j] = S[j]) do

{Цикл сравнения}

j := j + 1;

until (j > M) or (i > N - M);

if j > M then

StraightSearch := i + 1 {Успех}

else

StraightSearch := 0; {Неудача}

end; {StraightSearch}

Оценим эффективность прямого решения. Худшим случаем для данного алгоритма является такая ситуация, когда несовпадение с образцом обнаруживается только на последнем символе образца. Примером такого случая могут служить строки A = ‘aaaaaa ... aaa’ (nбукв ‘a’) иS = ‘aaa ... ab’ (m–1буква ‘a’ и одна буква ‘b’). Очевидно, при этом начинать сравнение придетсяn– m + 1раз, а цикл сравнения будет состоять изmитераций. Получаем оценку:T(n, m) = O(nm).

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

2. Алгоритм Кнута, Морриса и Пратта

Рассмотрим сначала более простой случай. Пусть все символы строки-образца Sразличны. Начнем сравнивать символыSслева направо с первымиmсимволами строкиA. Допустим, что несравнение символов произошло в позицииk  m, т.е. первыеk–1буквAиSсовпали. С какой позицииAследует начать новое сравнение сS? Поскольку символa_k–1 = s_k–1, тоa_k–1не может совпасть с предыдущими символамиS(потому что все символыSразличны). Значит, перед продолжением сравнения строк можно сдвинутьSтак, чтобы ее первый символ сравнивался сразу сk-м символомA(т.е. с той позициейA, где было обнаружено несовпадение).

Если в Sесть совпадающие символы, рассчитать величину сдвига несколько сложнее.

Определим d_jкак длину наибольшей подстроки изS, которая заканчивается в позицииjи совпадает с началом строкиSво всех позициях, кроме последней. Это можно подробно расписать таким образом:

s[j – d_j + 1] = s[1],

s[j – d _j + 2] = s[2],

… , (7.1)

s[j – 1] = s[d_j – 1],

но при этом s[j]  s[d_j]).

Если такой подстроки не существует, то положим d_j = 0. Тогда нетрудно показать, что, если первое несовпадение при сравнении символов изAиSпроизошло на паре символовa_i  s_j, то перед продолжением сравнения следует заменить индексjнаd_j, а значение индексаiне изменять (т.е. надо сдвинуть строкуSнаj – d_jпозиций вдоль строкиA). Действительно, поскольку символыa[i – d_j + 1],a[i – d _j + 2], … ,a[i – 1] успешно сравнились с символамиs[j – d_j + 1],s[j – d _j + 2], … ,s[j – 1], то они, согласно (7.1), должны сравниться и с символамиs[1],s[2], … ,s[d_j – 1], а потому сравнение можно продолжать с пары символовa[i] иs[d_j].

Если же значение jстало равно 0, то надо увеличитьiиjна единицу, т.е. начать сопоставление символов заново с позицииi + 1в строкеAи с первой позиции в строкеS.

Ниже приведены примеры значений d_j, рассчитанных для различных строк-образцов.

1)	a a a a a a	2)	q w e r t y u i
	0 0 0 0 0 0		0 1 1 1 1 1 1 1
3)	a a b a a b c	4)	a b c d a c e f a b d f
	0 0 2 0 0 2 4		0 1 1 1 0 2 1 1 0 1 3 1
5)	a b b a b b a c	6)	a b a b a b a c a b c
	0 1 1 0 1 1 0 5		0 1 0 1 0 1 0 6 0 1 3

Рассмотрим работу алгоритма на примере, показанном на рис. 7.1. В строкеA= ‘aabaabaaabaabc’ ищется подстрокаS= ‘aabaabc’ (см. выше, пример 3).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

A:

a

a

b

a

a

b

a

a

a

b

a

a

b

c

Шаг 1:

a

a

b

a

a

b

c

Шаг 2:

a

a

b

a

a

b

c

Шаг 3:

a

a

b

a

a

b

c

Рис. 7.1. Пример работы алгоритма Кнута, Морриса и Пратта

На первом шаге обнаруживается несовпадение букв a_iиs_jприi = 7 иj = 7. Выполняется присваиваниеj := 4. Сравнение продолжается, пока приi = 9 иj = 6 не происходит очередное несовпадение. Делается присваиваниеj := 2. На сей раз сравнение проходит успешно.

Отдельный вопрос – как лучше всего рассчитывать величины d_j. В алгоритме на этот вопрос дается довольно неожиданный ответ. Задачу расчетаd_jдля всех значенийjможно рассматривать как модифицированную задачу поиска, в которой роль строки поиска играетS, а роль строки-образца – начальная часть той же строки. Поэтому вычислениеd_jвыполняется примерно по тому же алгоритму, что и сам поиск вхожденияSвA.

Ниже приведен текст функции, реализующей алгоритм поиска КМП.

function KMPSearch(A: StringN; S: StringM): Integer;

var

i, j, k: Integer;

d: Array[1..M] of Integer;

begin

{Вычисление d[j]}

j := 1;

k := 0;

d[1] := 0;

while j < M do begin

while (k > 0) and (S[j] <> S[k]) do

k := d[k];

j := j + 1;

k := k + 1;

if S[j] = S[k] then d[j] := d[k]

else d[j] := k;

end;

{Поиск}

i := 1;

j := 1;

while (j <= M) and (i <= N) do begin

while (j > 0) and (A[i] <> S[j]) do

j := d[j];

i := i + 1;

j := j + 1;

end;

if j > M then

KMPSearch := i – j + 1 {Успех}

else

KMPSearch := 0; {Неудача}

end; {KMPSearch}

Можно доказать, что время работы алгоритма КМП T_макс(n, m) = O(n+m). Это значительно лучше, чем оценкаO(nm)для прямого поиска, особенно для длинных строк-образцов.