2.Префикс-функция. Определение

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

Математически определение префикс-функции можно записать следующим образом:

Например, для строки "abcabcd" префикс-функция равна:  , что означает:

у строки "a" нет нетривиального префикса, совпадающего с суффиксом;

у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;

у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;

у строки "abca" префикс длины 1 совпадает с суффиксом;

у строки "abcab" префикс длины 2 совпадает с суффиксом;

у строки "abcabc" префикс длины 3 совпадает с суффиксом;

у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.

Другой пример — для строки "aabaaab" она равна:  .

Z -функция от строки   и позиции   — это длина максимального префикса подстроки, начинающейся с позиции   в строке  , который одновременно является и префиксом всей строки  . Значение  -функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки. 

Алгоритм Кнута-Морриса-Пратта.

Постановка задачи

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

Рассмотрим сравнение строк на позиции  , где образец   сопоставляется с частью текста  . Предположим, что первое несовпадение произошло между   и  , где  . Тогда   и  .

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

Это приводит нас к следующему алгоритму: пусть   — префикс-функция от строки   для индекса  . Тогда после сдвига мы можем возобновить сравнения с места   и   без потери возможного местонахождения образца. Можно показать, что таблица   может быть вычислена (амортизационно) за   сравнений перед началом поиска. А поскольку строка   будет пройдена ровно один раз, суммарное время работы алгоритма будет равно  , где   — длина текста  .

Билет 4

Путь (Цепь) в графе   — последовательность вершин   при  , таких, что две любые последовательные вершины соединены хотя бы одной дугой из  .

Число   рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.

Построение матрица достижимости

Перемножение матриц

Пусть дан простой граф  , матрица смежности которого есть  , где  . Матрица смежности даёт информацию о всех путях длины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения   с самим собой:

.

По определению, матрица композиции отношений   есть  , где   —конъюнкция, а   — дизъюнкция.

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

Случай нескольких путей

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

Пример

Г раф 

Рассмотрим простой связный ориентированный граф . Он имеет матрицу смежности   вида:

Н айдём булевы степени этой матрицы  ,  ,  :

Получим матрицу достижимости

Таким образом, из вершины 1 можно добраться в любую другую.

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

Она показывает количество путей длины от 1 до 4 между вершинами орграфа.

2.Алгоритм Ахо — Корасик — алгоритм поиска подстроки, созданный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке. Время работы пропорционально  , где  — длина строки-образца,   — суммарная длина строк словаря, а   — длина ответа, то есть суммарная длина вхождений слов из словаря в строку-образец.