оценить как L(n)1+0(1\ где L(n) = eVlnnlnlnn ]\/[ет0д эллиптических кривых, предложенный Ленстрой [173], иногда эффективнее алгоритма квадратичного решета, поскольку он (так же как и р-алгоритм Полларда) быстро ищет небольшие делители; время поиска делителя р можно оценить как L(p)+01\

Поиск подстрок

Большинство текстовых редакторов умеет искать заданное слово в редактируемом тексте - хочется, чтобы это происходило быстро. Другой пример задачи, в которой требуется искать заданную последовательность символов в строке, - поиск данной цепочки ну-клеотидов в молекуле ДНК.

Говоря формально, задача поиска подстрок (string-matching problem) состоит в следующем. Пусть даны «текст» - массив Г[1..п] длины п и «образец» - массив Р[1..то] длины то. Мы считаем, что элементы массивов РиТ - символы некоторого конечного алфавита Е (например, Е = {0,1} или Е = {а, Ь,..., z}). Массивы, состоящие из символов алфавита Е, часто называют строками (strings) символов, или словами в этом алфавите.

Будем говорить, что образец Р входит со сдвигом s (occurs with shift s), или, эквивалентно, входит с позиции s + 1 (occurs beginning at position s + 1) в текст Г, если Osra - той T[s + l..s + то] = Р[1..то] (иными словами, если T[s + j] = P[j] при 1 j то). Если Р входит со сдвигом s в текст Г, то говорят, что s - допустимый сдвиг (valid shift), в противном случае s - недопустимый сдвиг (invalid shift). Задача поиска подстрок состоит в нахождении всех допустимых сдвигов для данных текста Г и образца Р (см. рис. 34.1).

Настоящая глава посвящена различным алгоритмам для поиска подстрок. В разделе 34.1 мы рассматриваем простейший алгоритм, работающий за время 0((п - то + 1)то) (в худшем случае). Затем в разделе 34.2 мы рассказываем об алгоритме Рабина - Карпа. Этот остроумный алгоритм поиска подстрок также в худ-

Рис.34.1. Переводы слов на рисунке: text - текст, pattern - образец.

Подпись:

Задача поиска подстрок. Требуется найти все вхождения образца Р = abaa в текст Г = abcabaabcabac. Образец входит в текст только один раз, со сдвигом s = 3 (стало быть, 3 - допустимый сдвиг).

Рис. 34.2

Подпись: Рис. 34.2. Доказательство леммы 34.1. Совпадающие символы соединены вертикальными линиями, а совпадающие части строк заштрихованы. Рис. (а) соответствует случаю ж \у\, рис. (б) - случаю \х\ \у\, рис. (в) - случаю \х\ = \у\.

шем случае работает за время О ((га - т + 1)т), но на практике он в среднем гораздо быстрее; кроме того, алгоритм Рабина - Карпа обобщается на другие задачи поиска образца. В разделе 34.3 мы описываем алгоритм поиска подстрок, который по заданному образцу строит конечный автомат, и затем пропускает через этот автомат текст Т. Время работы алгоритмов, основанных на этой идее, может быть доведено до О(га + тоЕ). Аналогичный, но более изощрённый алгоритм Кнута - Морриса - Пратта (сокращенно КМР) работает за время 0(т + га); этому алгоритму посвящен раздел 34.4. Наконец, в разделе 34.5 описывается алгоритм Бойера-Мура. Этот алгоритм зачастую оказывается наиболее удобным на практике, хотя, подобно алгоритму Рабина-Карпа, в худшем случае он не дает выигрыша по сравнению с простейшим алгоритмом.

34.0.1. Обозначения и терминология

Через Е* обозначается множество всех конечных строк над алфавитом Е, включая пустую строку (empty string), имеющую нулевую длину и обозначаемую е. Длина строки х обозначается \х\. Соединение, или конкатенация (concatenation) строк хну получится, если выписать строку ж, а за ней встык - строку у. Конкатенация строк хну обозначается ху; очевидно, \ху\ = \х\ + \у\.

Мы будем говорить, что строка w - префикс (prefix), или начало, строки ж, если ж = wy для некоторого у £ Е*. Будем говорить, что w - суффикс (suffix), или конец, строки ж, если ж = yw для некоторого у £ Е*. Будем писать w С ж, если w - префикс ж, и w □ ж, если w - суффикс ж. Например, ab С abcca и сса □ abcca. [С этими обозначеними нужно обращаться осторожно: а С Ь и Ь □ а означают совершенно разное!]

Пустая строка является префиксом и суффиксом любой строки; если w - префикс или суффикс ж, то \w\ ж. Для любых строк ж и у и для любого символа а соотношения ж □ у и ха □ уа равносильны; отношения С и □ транзитивны. В дальнейшем мы будем пользоваться следующей леммой.

Лемма 34.1 (Лемма о двух суффиксах)

Пусть ж, у и z - строки, для которых ж □ z и у □ z. Тогда ж □ у, если ж \у\; у □ ж, если ж \у\, и ж = у, если ж = \у\. Доказательство. См. рис. 34.2.

Если S*[l..r] - строка длины г, то ее префикс длины k г будет