188
правок
Изменения
Нет описания правки
p = link[p]
last = cur
==Применение==
===Проверка вхождения подстроки===
{{Задача
|definition =
Даны строки <tex>s</tex> и <tex>p</tex>. Требуется проверить, является ли строка <tex>p</tex> подстрокой <tex>s</tex>.
}}
Построим суффиксный автомат для строки <tex>s</tex>.<br>
Пусть текущее состояние {{---}} <tex>cur</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br>
Будем по очереди обрабатывать символы строки <tex>p</tex>. Если из состояния <tex>cur</tex> есть переход в по текущему символу, но перейдем в новое состояние и повторим процедуру. Если перехода не существует, то <tex>p</tex> не является подстрокой <tex>s</tex>. Если успешно обработали все символы <tex>p</tex>, то она является подстрокой <tex>s</tex>.<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
===Позиция первого вхождения строки===
{{Задача
|definition =
Даны строки <tex>s</tex> и <tex>p</tex>. Требуется найти позицию первого вхождения строки <tex>p</tex> в <tex>s</tex>.
}}
Построим суффиксный автомат для строки <tex>s</tex>.<br>
В процессе построения для каждого состояния <tex>q</tex> будем хранить значение <tex>first(q)</tex> {{---}} позицию окончания первого вхождения строки.
Поддерживать позицию <tex>first</tex> можно следующим образом: при добавлении нового состояния <tex>first(cur) = len(cur) - 1</tex>, а при клонировании вершины <tex>first(new) = first(q)</tex>.<br>
Для поиска вхождения обойдём автомат, как в предыдущей задаче. Пусть состояние <tex>p'</tex> в автомате соответствует строке <tex>p</tex>. Тогда ответ на задачу <tex>first(p') - |p| + 1</tex>.
<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
===Количество различных подстрок===
{{Задача
|definition =
Дана строка <tex>s</tex>. Найти количество различных подстрок строки <tex>s</tex>.
}}
Построим суффиксный автомат для строки <tex>s</tex>.<br>
Каждой подстроке в суффиксном автомате соответствует путь, тогда ответ на задачу {{---}} количество различных путей из начальной вершины. Так как суфавтомат представляет собой ациклический граф, мы можем найти [[Задача_о_числе_путей_в_ациклическом_графе|количество путей в графе методом динамического программирования]].
==Источники информации==
