A b a c a b a с a b c a b a c a b a b b

Вывод

Ввод

Пример

Строки

Строки являются одной из самых распространенных структур данных. Битовые строки соответствуют числам. Строки цифр образуют телефонные номера, строки символов – слова. Из слов состоят фразы, из фраз – документы и книги.

Программы выполняют самые разнообразные операции со строками. Строки можно сортировать, искать, анализировать. Распространенной задачей является формирование частотного словаря слов. Поиск повторяющихся подстрок лежит в основе многих архиваторов. Для выявления плагиатов находят длинные повторяющиеся подстроки в разных файлах. В данном разделе рассматриваются основные алгоритмы поиска заданной подстроки в тексте.

Многие задачи связаны с проблемой нахождения нужных слов в тексте. Современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов. Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня. Чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне.

В готовых подпрограммах далеко не всегда и не все написано лучшим образом. Во-первых, в стандартных функциях не обязательно используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте. Работа простейшего спам– фильтра, заключается в нахождении в тексте письма таких сочетаний слов, как ”работа с высокой оплатой” или “похудание за неделю”. Все вышесказанное говорит об актуальности проблемы, затрагиваемой в этом разделе.

Поставим сначала задачу в несколько упрощенном виде.

Поиск подстроки. Заданы две последовательности символов. Нужно определить все вхождения первой из них (назовем ее образец) во вторую (текст).

Ввод изфайла INPUT.TXT. Первая строка файла является образцом и имеет длину от 1 до 255. Вторая строка является текстом и имеет длину от 1 до 2´10⁹.

Вывод в файл OUTPUT.TXT. Вывести через пробел последовательность номеров позиций в тексте, начиная с которых в него входит образец. Нумерация начинается с 1. Если вхождений нет, вывести No.

AA

AAABAA

1 2 5

Из условия ясно, что образец можно запомнить в массиве символов, а текст – нельзя. Однако сначала для удобства предположим, что и образец, и текст хранятся в массивах P и T соответственно. Пусть M – длина образца, N – длина текста (M ≤ N).

Иногда требуется найти только первое вхождение образца. Дополнительным условием может быть отсутствие пересечений находимых подстрок текста.

Самое очевидное решение – сравнить образец с каждой из подстрок длины M, начинающихся в позициях 1, 2, …, N – M + 1. Такой алгоритм носит название последовательного или прямого [19]. Общее количество сравнений символов оценивается величиной O(M(N-M +1)). При заданных размерностях трудоемкость алгоритма допустима, но с ростом M и N быстро растет. Большинство сравнений в действительности лишнее. Например, если в каком-то многомегабайтном файле будет искаться последовательность длиной 100 Кб, то придется ждать очень долго.

Алгоритм Рабина [19] представляет собой модификацию линейного алгоритма. Он основан на весьма простой идее. Вырежем "окошечко" размером M и будем двигать его по тексту. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по всем буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины M. Тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.

Этот алгоритм выполняет линейный проход по образцу (M шагов) и линейный проход по всему тексту (N шагов), стало быть, общее время работы есть O (M+N). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда время работы алгоритма линейно зависит от размера строки и текста, значит, программа работает быстро. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые ”напоминают” образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию Hash, которая должна:

· легко вычисляться;

· как можно лучше различать несовпадающие строки;

· Hash(T[i+1, i+m]) должна легко находиться по Hash(T[i, i+m-1]).

Во время поиска будем сравнивать Hash(P) с Hash(T[i, i+M-1]) для i от 1 до N-M +1 включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

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

Однако, проблема в том, что искомая строка может быть длинной. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими, и работать с ними будет также неудобно. Но какой интерес работать только с короткими строками? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы.

Выберем некоторое число C (желательно простое) и некоторое натуральное число X (X< C). Каждое слово длины M будем рассматривать как последовательность целых чисел, заменив буквы их кодами. Эти числа будем считать как коэффициенты многочлена степени M - 1. Вычислим значение этого многочлена по модулю С в точке X. Это и будет одна из функций семейства (для каждой пары C и X получается своя функция). Сдвиг "окошечка" на одну позицию соответствует вычитанию старшего члена, умножению на X и добавлению свободного члена.

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число C фиксировано, а S и T - два различных слова длины M. Тогда им соответствуют различные многочлены. Совпадение значений функции означает, что в точке X эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени M -1 и имеет не более M -1 корней. Таким образом, если M много меньше C, то случайному значению X мало шансов попасть в "неудачную" точку. Строго говоря, время работы всего алгоритма в целом, есть O(M+N+AMN), но значение константы A достаточно невелико, так что сложность работы почти линейная.

Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими предварительными трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются оптимальными, поэтому мы перейдём к следующему классу алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска.

Алгоритм Кнута – Морриса – Пратта (КМП) [19] более полно использует информацию, полученную во время сканирования (алгоритм последовательного поиска ее просто выбрасывает). После сдвига образца по тексту стоит вести сравнение посимвольно. Если не совпал первый символ, нет смысла переходить к следующему. Хотелось бы сдвигать образец так, чтобы обеспечить совпадение максимального числа начальных символов образца и подстроки из «окошка». Оказывается, это можно обеспечить путем предварительного исследования образца. Будем следовать описанию алгоритма в [3], объясняя некоторые этапы.

Пусть в i -й позиции текста отмечено несовпадение с текущим символом образца, а в предыдущих j позициях символы текста и образца совпадают. Иными словами, P_{j+ 1} ≠ T_i, а P₁P₂... P_j = T_i-jT_i-j+1... T_{i- 1}. На какое максимальное число позиций можно сдвинуть образец, не рискуя пропустить его вхождение в текст? Очевидно, нужно найти в позициях текста от i – j + 1 до i -1 максимальное совпадение с началом образца. Но поскольку текст в этих позициях совпадает с символами образца, то это эквивалентно нахождению самого длинного начала образца P₁P₂... P_k ( 1 < k < j), которое повторяется в оставшейся части образца, т.е. P ₁ P ₂... P_k = P_{s+ 1} P_{s+ 2}... P_s+k.

Если сдвинуть образец на s позиций, то мы обеспечим совпадение в позициях текста от i – j + s до i – j + s + k. Докажем, что полное совпадение может быть только в том случае, когда подстрока P ₁ P ₂... P_k входит как в начало, так и в конец строки P ₁ P ₂... P_j, т.е. s+k=j. Предположим обратное: после сдвига на s позиций образец полностью совпадает с подстрокой текста и s+k < j, как это показано на рисунке.

……

Ti-j. …...........

Ti-j+s ………... Ti-j+s+k … Ti- 1

Ti …

P 1 P 2 …….. ... Ps

Ps+ 1.... Ps+k

Ps+k+ 1 … Pj

Pj+ 1…

P 1.. ….. Pk

Pk+ 1 ….. Pj-s

Pj-s+ 1…

В силу полного совпадения, T_i-j+s+k = P_{k+ 1}, а поскольку T_i-j+s+k = P_{s+k+ 1}, то P_{s+k+ 1} = P_{k+ 1}. Мы получили в позициях от 1 до j образца повторение первых k + 1 начальных символов. Это противоречит выбору самого длинного начала из k символов.

Итак, подстрока P₁P₂…P_k входит как в начало, так и в конец строки P₁P₂... P_j. Сдвинем образец сразу на j - k позиций. Поскольку k < j, первые k символов образца и текущего “окошка” совпадут. Это состояние показано на следующем рисунке.

……

Ti-j …………

Ti-j+s …………………… Ti- 1

Ti …

P 1 P 2……… Ps

Ps+ 1.. ………………... Ps+k

Pj+ 1…

P 1.. …………………… Pk

Pk+ 1…

Если P_{k+ 1} = T_i, то можно продолжить сравнение, начиная с символа T_{i+ 1}. Если же P_{k+ 1} ≠ T_i, то снова будем находить самое длинное начало образца P₁P₂…P_r ( 1 < r < k), которое повторяется в последних позициях подстроки P ₁ P ₂... P_k.

Эти свойства образца можно рассчитать заранее. Если для каждой позиции j образца известна максимальная длина f(j) < j начала образца, совпадающая с концом строки P ₁ P ₂ …P_j, то возможен сдвиг образца вперед на j - f(j) позиций без последующего возврата назад. Отсутствие возвращений в тексте позволяет не запоминать его в массиве.

Функция f(j) называется функцией возвратов. Она показывает, к какому символу P_f(j) нужно возвратиться в образце, когда P_{j+ 1} ≠ T_i. Это эквивалентно сдвигу образца вправо относительно текста на j - f(j) позиций и следующему сравнению P_f(j) с T_i.

Как вычислять функцию возвратов? Очевидно, f (1)=0. Пусть вычислены f (1),…, f (j -1) и f (j -1) = k. Если P_j = P_{k+ 1}, то конец строки P₁P₂... P_j совпадает с ее началом длины k +1, поэтому f (j) = k +1. Если P_j ≠ P_{k+ 1}, то «следующим концом» строки может быть подстрока P ₁ P ₂ …P_{f ( k )} P_{f ( k )+1}, поскольку именно P₁P₂... P_{f ( k )} является самым длинным концом P ₁ P ₂... P_k образца, совпадающим с его началом. Если и эта строка не годится, то следующей подстрокой может быть P ₁ P ₂... P_{f(f(k)) +1} и т. д. Таким образом, или будет найдено начало длины r, при котором P ₁ P ₂... P_r является концом P ₁ P ₂… P_j, и тогда f (j) = r, либо такого начала найдено не будет, и тогда f (j) = 0.

Приведем пример. В первой строке содержится текст, во второй – образец, в третьей значения функции возврата

Дата добавления: 2014-01-11