обозначаться Sk = 5[1../г] (в частности, So = е и Sr = S). В этих обозначениях задача о нахождении образца Р длины то в тексте Г длины га состоит в нахождении всех таких s из промежутка 0 s га - то, что Р □ Ts+m.

При записи алгоритмов для поиска подстрок мы будем рассматривать проверку равенства двух строк как элементарную операцию, время выполнения которой пропорционально длине сравниваемых строк. Если сравнивать строки слева направо и останавливаться, как только обнаружено расхождение, то стоимость сравнения строк хну есть Q(t + 1), где t - длина наибольшего общего префикса строк хну. (Мы пишем t + 1 вместо t, учитывая сравнение первых не совпавших символов.)

34.1. Простейший алгоритм

Первый приходящий в голову алгоритм для поиска образца Р в тексте Г последовательно проверяет равенство Р[1..то] = T[s + l..s + то] для всех п - то + 1 возможных значений s:

Iaive-String-Matcher(T,P)

1n \gets length[Т]

2m \gets length[P]

3for s \gets 0 to n-m

4do if P[l..m]= T[s+l..s+m]

5then print Подстрока входит со сдвигом s

Можно сказать, что мы двигаем образец вдоль текста и проверяем все его положения (рис. 34.3). Отметим, что проверка в строке 4 представляет собой ещё один цикл.

Время работы процедуры Naive-String-Matcher в худшем случае есть О ((га - то + 1)то). В самом деле, пусть Т = ап (буква а, повторённая га раз), а Р = ат. Тогда для каждой из га - то + 1 проверок (строка 4) будет выполнено то сравнений символов, всего (га - то + 1)то, что есть ©(га2) (при то = [га/2]).

Простейший алгоритм - не лучший (далее мы расскажем об алгоритме, работающем за время 0(га+ то)). Неэффективность про-

Рис. 34.3 Подпись:

Рис. 34.3. Простейший алгоритм ищет образец Р = aab в тексте Г = acaabc. Четыре последовательные попытки изображены на рис. (а)-(г). Буквы, для которых сравнение прошло успешно, соединены и показаны серым. Буквы, на которых выявлено несовпадение, соединены ломаными линиями. При этом s = 2 - единственный допустимый сдвиг.

стейшего алгоритма связана с тем, что информация о тексте Г, получаемая при проверке данного сдвига s, никак не используется при проверке последующих сдвигов. Между тем такая информация может очень помочь. Пусть, например, Р = aaab и мы выяснили, что сдвиг s = 0 допустим. Тогда сдвиги 1, 2 и 3 заведомо недопустимы, поскольку Г[4] = Ь. Далее мы обсудим различные способы реализации этой идеи.

Упражнения

34.1-1

Какие сравнения символов делает простейший алгоритм при Р = 0001 и Г = 000010001010001? 34.1-2

Покажите, что в худшем случае простейший алгоритм найдёт первое вхождение подстроки за время в ((га - т + 1)(т - 1)). 34.1-3

Пусть все символы в образце Р различны. Как усовершенствовать алгоритм Naive-String-Matcher, чтобы он работал за время О (га), где га - длина текста?

34.1-4

Пусть алфавит содержит d символов, и пусть образец и текст - случайные строки длины тип соответственно. Покажите, что математическое ожидание числа сравнений символов, производимых простейшим алгоритмом при выполнении строки 4, есть

1 d~m

(га - т + 1)---p-j- 2(га - т + 1)

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

34-1.5 Пусть в образце (но не в тексте!) может встречаться, наряду с символами из алфавита Е, символ ф, называемый символом пропуска (gap character), который соответствует произвольной подстроке (в том числе пустой). Например, образец аЬфЬафс входит в текст cabccbacbacab и как

ab 0 ba 0с

и как

cabccbacbaс уаЪ.

ab <> ba <>с

Разработайте полиномиальный алгоритм, выясняющий, входит ли данный образец (с символами пропуска) в данный текст.

34.2. Алгоритм Рабина - Карпа

Рабин и Карп изобрели алгоритм поиска подстрок, который эффективен на практике и к тому же обобщается на другие аналогичные задачи (например, поиск образца на двумерной решётке). Хотя в худшем случае время работы алгоритма Рабина-Карпа есть в ((га - то + 1)т), в среднем он работает достаточно быстро.

Предположим для начала, что Е = { 0, 1, 2,..., 9 } (в общем случае можно считать, что каждый символ в алфавите £ есть d-ичная цифра, где d = £). Тогда строку из к символов можно рассматривать как десятичную запись числа (/г-значного), а сами символы - как цифры.

Если Р[1..то] - образец, то через р обозначим число, десятичной записью которого он является; аналогично, если Г[1..га] - текст, то для s = 0,1,..., га - то обозначим через ts число, десятичной записью которого является строка T[s + 1..S+ тп]. Очевидно, s является допустимым сдвигом тогда и только тогда, когда ts = р. Если бы мы могли вычислить р за время О (то) и все £г- за время О (га) (временно закроем глаза на то обстоятельство, что эти вычисления могут привести к слишком большим числам), то мы смогли бы найти все допустимые сдвиги за время О (га), сравнивая р со всеми ts по очереди.

Вычислить р за время О (то) действительно можно, по схеме Гор-нера (разд. 32.1):

р = Р[т] + 10(Р[то - 1] + 10(Р[то - 2] + • • • + 10(Р[2] + 10Р[1]) ...)).

Точно так же за время О (то) можно вычислить to.

Чтобы вычислить t\, £2, • • •, t-n-m за время 0(га - тп), заметим, что при известном ts можно вычислить ts+i за время 0(1). В самом деле,

ts+1 = 10(ts - Ю"1"1! + 1]) + T[s + то + 1] : (34.1)

чтобы получить строку T[s + 2..s + то + 1] из T[s + l..s + то], надо удалить T[s + 1] (то есть вычесть 10m 1T[s + 1] из ts) и приписать справа T[s + то + 1] (то есть умножить полученную разность на 10 и прибавить к ней T[s + то + 1]). Если вычислить константу 10m 1 заранее (с помощью техники, описанной в разд. 33.6, это можно сделать за время O(lgrre); впрочем, оценка не ухудшится, если непосредственно перемножить то - 1 десятку за время О (то)), то стоимость вычислений по формуле (34.1) ограничена сверху константой; стало быть, числа р и to, t\,..., tn m могут быть найдены за время О (га + то), и также за время О (га + то) могут быть найдены все вхождения образца Р[1..то] в текст Г[1..га].

До сих пор мы не учитывали того, что числа р и ts велики - настолько, что предположение о выполнении арифметических one-