Поиск текстовых строк

При обработке текстов очень часто приходится выполнять поиск текстовых строк. Строка является массивом из элементов типа CHAR:
STRING[20] º ARRAY[0..20] OF CHAR. В то же время у строки есть переменная длина – она не обязана заполнять весь отведенный под нее кусок памяти. Значит, длину строки надо каким-то образом хранить. Исторически сложилось два подхода к хранению длины строки:

1. Как в Паскале – длина строки явно записана в нулевом элементе массива. Недостаток: длина ограничена 255 символами. Достоинство: длина всегда доступна

2. Как в С: строка заканчивается символом с кодом 0 (ASCIIZ-строки). Недостаток: символ 0 нужно обрабатывать особым образом, сложно искать длину строки. Достоинство: длина строки фактически не ограничена.

Кстати, в языке Delphi есть оба типа строк.

Задача поиска в строке формулируется так: найти, с какой позиции i в строке S содержится строка P. Например, если S:=‘промышленность’, а P:=‘мыш’, то i = 4. Алгоритм выглядит так:

{ N,M – длины строк строк s и р соответственно }
I := -1;
REPEAT
INC(I); j := 0;
WHILE (j<M) AND (s[I+j]=p[j]) DO
INC(j);
UNTIL (j=M) OR (I=N-M)

Если по окончании цикла j=M – подстрока в строке найдена!

Приведенный алгоритм работоспособен, не неэффективен. В 1970 был предложен алгоритм Кнута-Морима-Пратта. Его идея состоит в том, что после частичного совпадения строк можно двигаться вдоль строки быстрее, чем на один символ. Например, ищем строку 'abc' в строке 'abeabeabeabc'. Первые две буквы совпадут, а третья – нет. После этого можно продолжать сравнение не со второй позиции, а сразу с четвертой. Схема алгоритма такова:

I := 0; j : = 0;
WHILE (j<M) AND (I<N) DO
BEGIN
WHILE (j>=0) AND (s[I]<>p[j]) DO
BEGIN
… { расчет D }
j : = D { D – величина сдвига }
END;
INC(I); INC(j)
END;

Наибольшую трудность представляет вычисление величины сдвига D. Рассчитывается она довольно сложным образом, который подробно рассмотрен в [1].

К вопросу сравнения строк можно подойти и с другой стороны, причем в буквальном смысле слова. Алгоритм Боуера – Мура сравнивает строки не с начала, а с конца. В этом есть большой смысл: слова, как правило, имеют длинные общие корни и короткие окончания. Сравнивая "обороноспособность" и "обороноспособности" с начала, мы установим их неравенство, лишь перебрав 17 букв. При сравнении же с конца достаточно сравнить "ь" и "и". Алгоритм сравнения с конца приведен ниже:

I := M; j : =M;
WHILE (j>0) AND (I<N) DO
BEGIN
J : =m; K : =I;
WHILE (J>0) AND (s[k-1]=P[j-1]) DO
BEGIN
DEC(K); DEC(J)
END;
I : = I+d[s[I-1]];

END;