Алгоритм Бойера – Мура [9] имеет нелинейную оценку трудоемкости в худшем случае, но в среднем работает быстрее. Здесь можно провести аналогию с широко известным алгоритмом быстрой сортировки Хоара [1, 3, 5, 7, 11], который имеет квадратичную трудоемкость на специально подобранных данных. Этот алгоритм считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее мы совмещаем начала строки и образца и начинаем проверку с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. При несовпадении очередного символа величина сдвига определяется выражением L - K, где L – значение из таблицы смещений, а K – количество совпавших символов. После сдвига снова начинаем проверку с последнего символа.

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

Величина сдвига в случае несовпадения символа вычисляется, исходя из следующих соображений: сдвиг образца должен быть минимальным, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, мы смещаем образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце.

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Если символ отсутствует в образце, то заносится значение M.

Поясним все вышесказанное на простом примере. Пусть у нас есть алфавит из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца abaad в строке abecdacbbdbabaad. Длина образца M = 5. Таблица смещений будет выглядеть так:

a b c d e

1 3 5 0 5

Начало поиска ведется с первой позиции:

a b e c d a c b b d b a b a a d

a b a a d

Последний символ образца совпадает с наложенным символом d строки, а предпоследний нет, то есть K =1. Из таблицы смещений для символа c строки находим L = 5. Сдвигаем образец вправо на L - K = 4 позиции:

a b e c d a c b b d b a b a a d

a b a a d

Последний символ образца не совпадает с символом b строки, значит K =0, а L = 3. Сдвигаем образец вправо на L - K = 3 позиции:

a b e c d a c b b d b a b a a d

a b a a d

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

a b e c d a c b b d b a b a a d

a b a a d

Теперь в соответствии со смещением для символа b из таблицы сдвигаем образец на 3 позиции и получаем искомое вхождение образца:

a b e c d a c b b d b a b a a d

a b a a d

Для кодовой таблицы, состоящей из 256 символов, таблица смещений будет представлять собой массив целых чисел, индексы которого изменяются от 0 до 255 и соответствуют кодам символов. Имеется много модификаций описанного алгоритма [9, 10]. Некоторые из них строятся на основе использования теории конечных автоматов.

Эффективность алгоритма Бойера – Мура в среднем выше по сравнению с алгоритмом КМП, но существенно зависит от длины текста и длины образца. Так при длине строки до 10 символов он показывает себя хуже, даже чем последовательный поиск. Алгоритм КМП менее чувствителен к размерности текста и образца. Его можно использовать как универсальный, когда неизвестны длины строки и образца.

Алгоритм Рабина работает быстрее последовательного, но медленнее КМП, однако простота и малые трудозатраты на реализацию делают его привлекательным для использования в неспециальных программах.

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

Мы рассматривали точное совпадение символов образца и текста. Существует много разновидностей неточного поиска [10]. Например, можно не учитывать окончаний слов, искать по нескольким образцам, допускать наличие символов, не принадлежащих образцу и т. п.

Задачи для самостоятельного решения

12.1. Алгоритм Рабина (6)

Требуется найти все вхождения образца в текстовом файле методом Рабина. Образец может включать пробелы и распространяться на разные строки файла. Конец строки файла может интерпретироваться как пробел, если строка не заканчивается знаком переноса.

Ввод из файла INPUT.TXT. Первая строка файла является образцом и имеет длину от 1 до 255. Вторая строка задает имя текстового файла и имеет неограниченную длину.

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

12.2. Алгоритм Кнута – Морриса – Пратта (6)

Требуется найти все вхождения образца в текстовом файле методом КМП. Образец может включать пробелы и распространяться на разные строки файла. Конец строки файла может интерпретироваться как пробел, если строка не заканчивается знаком переноса.

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

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

12.3. Алгоритм Бойера – Мура (6)

Требуется найти все вхождения образца в текстовом файле методом Бойера – Мура. Образец может включать пробелы и распространяться на разные строки файла. Конец строки файла может интерпретироваться как пробел, если строка не заканчивается знаком переноса.

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

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

12.4. Поиск по нескольким образцам методом КМП (4)

Требуется найти все вхождения любого из образцов в текст.

Ввод из файла INPUT.TXT. Первая строка файла определяет количество образцов N. В следующих N строках задаются образцы. Каждый из них имеет длину от 1 до 255. Последняя строка является текстом, в котором ищутся образцы, и имеет длину от 1 до 210⁹.

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

Пример

Ввод

2

AA

ABA

AAABAA

Вывод

AA 1

AA 2

ABA 3

AA 5

12.5. Сравнение алгоритмов поиска подстрок (7)

Требуется сравнить эффективность алгоритмов последовательного поиска, Рабина, КМП и Бойера – Мура для строк образцов и текстов разных длин путем случайной генерации строк из

1. символов;

2. слов заданного списка.

12.6. Строка (4)

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

Ввод из файла INPUT.TXT. В первой строке записана длина заданной строки N (1 ≤ N ≤10⁶). Во второй строке - N заглавных латинских букв, определяющих заданную строку.

Вывод в файл OUTPUT.TXT. В единственную строку вывести подстроку с наибольшим количеством букв, встречающихся один раз.

Примеры

Ввод 1 Ввод 2 Ввод 3

5 5 6

ABBAC OLYMP DACDAC

Вывод 1 Вывод 2 Вывод 3

BAC OLYMP ACD

12.7. Кроссворд (6)

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

Ввод из файла INPUT.TXT. В первых четырех строках записаны слова, состоящие из заглавных латинских букв. Длина каждого слова до 20 символов.

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

Пример

Ввод

STAMPING

FORMULA

STOP

SPELING

Вывод

*****S***

*STAMPING

*T***E***

FORMULA**

*P***I***

*****N***

*****G***

13. Графы

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

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

Приведем некоторые определения.

Неориентированный граф связен, если существует хотя бы один путь между каждой парой вершин.

Ориентированный граф связен, если связен неориентированный граф, получающийся путем удаления ориентации ребер.

Ориентированный граф сильно связен, если для каждой пары вершин существуют пути как из первой вершины во вторую, так и из второй вершины в первую.

Максимальный связный подграф называется связной компонентой графа. По аналогии, максимальный сильно связный подграф называется сильно связной компонентой графа.

Связность графа выявляется проще всего обычным поиском в глубину из произвольной начальной вершины. Посещаемые вершины помечаются с тем, чтобы повторно в них не заходить. Если в конце все вершины оказываются помеченными, то граф связен. Поскольку при поиске в глубину каждое ребро проходится только дважды, то общая трудоемкость этого метода составляет O(V+E), где V – количество вершин графа, а E – количество ребер.

Если граф несвязен, то часто требуется выделить все компоненты связности. Для этого достаточно использовать различные метки. Выберем произвольную начальную вершину и обойдем в глубину компоненту связности, включающую эту вершину. Затем выберем любую непомеченную вершину и выделим таким же образом следующую компоненту. Будем повторять эти действия, пока не окажутся помеченными все вершины графа.

Выделение сильно связных компонент происходит несколько сложнее. Пусть T – некоторая вершина ориентированного графа. Обозначим через R(T) множество вершин, достижимых из вершины T, а через Q(T) – множество вершин, из которых существует путь в вершину T. Оказывается, что пересечение множеств R(T) и Q(T) вместе с соответствующими дугами является множеством вершин графа, составляющим вместе с инцидентными им дугами сильно связную компоненту [4]. После пометки всех ее вершин можно находить следующие сильно связные компоненты.

Иногда недостаточно знать, что граф связен. Может возникнуть вопрос, насколько "сильно” связан граф. Например, в графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения. Граф без точек сочленения называется двусвязным. Максимальный двусвязный подграф графа называется двусвязной компонентой.

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

Трудоемкость этого метода O(V²+VE). Существует алгоритм выделения точек сочленения и двусвязных компонент с трудоемкостью O(V+E) [1, 8].

Рассмотрим следующую задачу.