Те, кто имеет несчастье часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Господа программисты тоже это знают, благо вплоть до самой компиляции программы им приходится работать в текстовом редакторе.
Впрочем, мы с вами собрались не затем, чтобы расхваливать эту почтенную фичу, а чтобы разобраться, как это работает и как это можно реализовать на практике. Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня — чтобы установить цензуру на своем чате, вы, скорее всего, воспользуетесь уже готовым скриптом. Но если вдруг вы задумаете писать принципиально новый редактор, знать принципы организации функций поиска будет совсем нелишне. Кроме того, в готовых самплах тоже далеко не всегда все написано лучшим образом. Наконец, область применения функции поиска, как вы понимаете, не ограничивается одними лишь текстовыми редакторами…
Итак, пусть у нас есть текст, состоящий из n символов, который в дальнейшем договоримся называть T, а T[i] — его i-ый символ. Строку или просто слово, состоящее из m символов, назовем S, где S[i] —i-ый символ строки. Нам нужно проверить, входит ли данная строка в данный текст, и если входит, то начиная с какого символа текста. В этой статье мы рассмотрим несколько известных алгоритмов, решающих поставленную задачу.
Простейший алгоритм
Суть метода, о котором пойдет речь ниже, заключается в следующем: мы проверяем, совпадают ли m символов текста (начиная с выбранного) с символами нашей строки, пытаясь примерить шаблон куда только возможно (Рис. 1). Естественно, реализовать описанный алгоритм проще всего (код на языке Pascal):
Program SimpleSearch; Var T : array[1..40000] of char; {выполняет роль текста} S : array[1..10000] of char; {выполняет роль строки; как и текст, может быть достаточно велика} i,j : longint; m,n : longint; Begin {Ввод текста и образца} … for i:=1 to n-m+1 do begin j:=0; while (j0) and (S[k+1]<>S[i]) do k:=P[k]; {значение функции может быть получено из ранее сделанных вычислений} if S[k+1]=S[i] then k:=k+1; P[i]:=k; {присвоение префикс-функции} end; End; …
Теперь разберемся, почему же данная процедура вычисляет префикс-функцию 
правильно. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]0) and (S[k+1]<>T[i]) do k:=P[k]; if S[k+1]=T[i] then k:=k+1; if k=m then {если совпали все символы} begin writeln('Образец входит в текст начиная с ',i-m+1,'-ого символа'); k:=P[k]; end; end; End.`
Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.
Напоследок хочу заметить, что простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считают, сколько символов совпало в процессе работы. И еще: алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее. Так что делайте выводы.
P.S. Все программы проверены на работоспособность, достаточно вставить соответствующие сегменты кода вместо многоточий.