-1. Отделимость от конуса (осталось с прошлого раза) 0. Про автоматы 0.1 регулярные языки 0.2 def суф. автомат 0.3 в минимальном автомате состояний столько же сколько правых контекстов 1. Суф. Автомат 1.1 Lm0: а суффикс b => R(a) subseteq R(b) 1.2 Lm1: правые контексты вложены или непересекаются 1.3 Lm2: внутри одного правого контекста всё суффиксы друг друга, и дырок нет 1.4 Понятие суфссылки, смотрим на расширение нашего пр. контекста при сужении. 1.5 Терминальные вершины 2. Пример автомата: abb 3. Построение 3.1 Lm о связи SA(s) и SA(sa) 3.2 Вершина может сплититься и не сплититься. 3.3 Если не сплитится, то делать с рёбрами не надо 3.4 Сплитнется не более чем одна вершина 3.5 Само построение 4. Линейность: 4.1 Число вершин 4.2 Число рёбер (сплошные/несплошные), дерево сплошных рёбер 4.3 Оценка O(n) на переходы по суффсылкам 5. Задачи 5.0 Число подстрок [static] 5.1 IsSubstring query 5.2 Самая длинная строка с двумя вхождениями без наложений 5.3 LZSS 5.4 Common Substring: через s1 #1 .. sk #k 5.5 Common Substring: более быстрое решение через автомат от одной строки