Семинар 1.

1.	Задача: хотим научиться искать в строке S заданную подстроку T.
	Наивный алгоритм работает за O(|S|⋅|T|), а мы хотим за O(|S|+|T|).
	Такую асимптотику обеспечивает алгоритм Кнута-Морриса-Пратта.
	Алгоритм заключается в следующем: мы прикладываем шаблон T
	к строке S и двигаемся по S, пока S и T совпадают.
	Если мы дошли до конца T, то подстрока найдена.
	Как только мы нашли несовпадение в S и Т, мы двигаем шаблон T
	вперёд вдоль строки S так чтобы начало T опять совпало с S
	до текущего положения (не включая его). При этом мы стремимся
	подвинуть T как можно меньше, чтобы не пропустить совпадений.
	Затем мы снова сравниваем S и T в текущем положении. Если они
	совпали, переходим к следующему символу S, если нет, то опять
	двигаем T. И так далее.

2.	Заметим, что куда нужно двигать T зависит только от текущего
	положения в T. Действительно, пусть длина совпавших подстрок
	S и T равна i, a S' — обработанная часть строки S, тогда нам
	нужно найти максимальный собственный префикс T[1:i], который
	является суффиксом S'. Но так как T[1:i] сама суффикс S', то
	нам нужно найти максимальный собственный префикс T[1:i],
	являющийся его же префиксом. Функция p(i), возвращающая длину
	максимального собственного префикса строки, являющегося его
	суффиксом, называется префикс-функцией. То есть, теперь для
	работы алгоритма нам нужно найти префикс-функцию шаблона T.

3.	Префикс-функция вычисляется индуктивно: пусть мы посчитали
	p(i) для i = 1...k, хотим посчитать для k+1. Мы знаем, что
	у нас только что закончился суффикс длины p(k), являющийся
	префиксом. Сравним T[k+1] и T[p(k)+1]. Если они совпали, то
	теперь у нас суффикс длины p(k)+1, являющийся префиксом,
	то есть p(k+1) = p(k)+1. Если не совпали, то пытаемся взять
	суффикс-префикс поменьше. Следующий по убыванию длины такой
	суффикс будет иметь длину p(p(k)). Опять сравниваем T[k+1]
	и T[p(p(k))+1], если совпали, то p(k+1) = p(p(k))+1, иначе
	берём суффикс длины p(p(p(k))), и так далее.

4.	Несмотря на то что в каких-то шагах вычисления префикс-
	функции, а также непосредственно поиска мы можем делать
	довольно много итераций для уменьшения длины текущего
	префикса-суффикса, общее число действий всё равно будет
	линейно. Действительно, так как p(i) < i, а i ⩾ 0, то на
	каждое уменьшение длины суффикса (переход от i к p(i)),
	когда-то было её увеличение (переход от i к i+1), значит
	суммарно переходов от i к p(i) не больше, чем общая длина
	строки.

5.	Вместо того, чтобы сначала считать префикс-функцию для T,
	а потом с помощью неё искать T в S, можно применить такой
	хитрый приём: начнём считать префикс-функцию для строки
	T#S, где # — особый символ, который не встречается в T,
	тогда как только префикс-функция станет равна длине T,
	у нас будет найдено вхождение T в S.

6.	Теперь мы ищем в строке S не одну подстроку, а сразу несколько.
	Для этого мы строим из искомых слов бор — дерево, на рёбрах
	которого написаны буквы, так что идя от корня до какого-нибудь
	листа, мы прочитаем одно из наших слов. При этом, из каждой
	вершины должно выходить не более одного ребра, с каждой буквой
	(то есть рёбра, выходящие из одной вершины с одной и той же
	буквой, склеиваются).
	Каждой вершине соответствует путь до неё из корня дерева и
	строка, состоящая из букв, записанных на рёбрах этого пути.
	Для удобства будем в дальнейшем отождествлять вершину и
	соответствующую ей строку.

7.	Мы снова идём по строке S и параллельно идём по дереву. Если
	из текущей вершины выходит ребро с текущей в S буквой, то мы
	по нему проходим. Если не выходит, то мы так же как и раньше
	хотим найти в дереве максимальный собственный суффикс, совпавшей
	ранее подстроки. И попробовать пройти по текущей букве из
	этого суффикса. Если получилось — хорошо, нет — находим
	максимальный собственный суффикс этого суффикса, и так далее.
	Оказывается, как и раньше, все эти переходы можно предпосчитать
	как только построим бор.

8.	Мы добавим в наш бор суффиксные ссылки — из каждой строки
	будет выходить стрелка, указывающая, куда следует перейти,
	если ребро с нужной буквой не выходит из этой вершины, а
	именно, в максимальный собственный суффикс этой строки,
	который есть в дереве.
	Заметим, что любая суффиксная ссылка идёт на уровень более
	близкий к корню, чем вершина, из которой она выходит — это
	следует из определения.
	Для удобства, суффиксная ссылка из корня будет вести в корень.
	Строить суффиксные ссылки будем поочерёдно для каждого уровня,
	начиная с корня. Чтобы построить суффиксную ссылку для вершины
	v, мы идём в её родителя p, и смотрим, по какому символу мы
	перешли из p в v. Затем идём по суффиксной ссылке (она уже
	есть!) из p в w, и смотрим, есть ли из w ребро, помеченное c.
	Если есть, то в вершину, находящуюся на конце этого ребра,
	пускаем суффиксную ссылку из v. Иначе опять переходим из w
	по суффиксной ссылке, и так далее, пока не дойдём до вершины,
	из которой выходит ребро, помеченное буквой c.
	Аналогично оценке для префикс-функции, можно показать, что
	построение бора и суффиксных ссылок линейно по сумме длин
	искомых строк.

9.	Теперь, имея, в руках такой бор с суффиксными ссылками, мы
	можем искать в тексте строки, из которых он был построен.
	Для этого ещё нужно пометить вершины, в которых заканчивались
	слова из нашего набора. Теперь, на каждом шаге, из текущей
	вершины ходим по суффиксным ссылкам до корня. Каждую помеченную
	вершину, встретившуюся на этом пути, добавляем в ответ.
	Однако, такое решение займёт O(|S|⋅max(|Ti|)). Его можно
	улучшить. Для этого, в каждую вершину добавим ссылку на
	ближайшую достижимую по суффиксным ссылкам помеченную вершину.
	После этого, время станет линейным по длине S плюс количество
	найденных подстрок.
	Это был алгоритм Ахо-Корасик.