1.4. Прямой поиск строки
 

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки. Его можно определить следующим образом. Пусть задан массив s из N элементов и массив р из М элементов, причем 0 < М ≤ N. Описаны они так:
char s[N-1], p[M-1];

Поиск строки обнаруживает первое вхождение р в s. Обычно s можно считать некоторым текстом, а р - образом или словом, и мы хотим найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов, отсюда и очевидная заинтересованность в поиске эффективного алгоритма для этой задачи. Однако прежде, чем обращать внимание на эффективность, давайте сначала разберём некий "прямолинейный" алгоритм поиска. Мы его будем называть прямым поиском строки.

Еще до определения алгоритма нужно более точно сформулировать, что же мы от него желаем получить. Будем считать результатом индекс i, указывающий на первое с начала строки совпадение с образом. С этой целью введем предикат Р(i,j):
Р(i,j)=A_k: 0≤k<j: s_i+k=p_k.

Наш результирующий индекс, очевидно, должен удовлетворять этому предикату P(i, М). Но этого недостаточно; Поскольку поиск должен обнаружить первое вхождение образа, P(k, M) но быть ложным для всех k < i. Обозначим это условие через Q(i):
Q(i)= A_k: 0≤k<i: ~P(k,M).

Поставленная задача сразу же наводит на мысль оформить поиск как повторяющееся сравнение. Вычисление Р, естественно, вновь сводится к повторяющимся сравнениям отдельных символов. Если применить к Р теорему Моргана, то получается, что итерации должны "искать" несовпадение между образом и строкой символов.
P(i,j)=( A_k: 0≤k<j: s_i+k=p_k)= (~E_k:0≤k<j: s_i+k!=p_k).

В результате этого уточнения мы приходим к повторению внутри повторения. Предикаты Р и Q включаются в соответствующие места программы как примечания. Они представляют собой инварианты циклов упомянутых итеративных процессов.

Анализ прямого поиска в строке. Этот алгоритм работает достаточно эффективно, если мы допускаем, что несовпадение пары символов происходит, по крайней мере, после всего лишь нескольких сравнений во внутреннем цикле. При большой мощности типа это достаточно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае производительность будет внушать опасение. Возьмем, например, строку, состоящую из N - 1 символов А и единственного В, а образ содержит М - 1 символов А и опять В. Чтобы обнаружить совпадение в конце строки, требуется произвести порядка N* М сравнений. Однако, есть прием, который существенно улучшает обработку этого неблагоприятного варианта.