Суффиксный автомат и суффиксное дерево: что они решают и когда какое брать (обзорно)?
В разборах мелькают «суффиксный автомат» и «суффиксное дерево», и я не понимаю, чем они отличаются концептуально и какие задачи закрывают. Не нужен полный код — нужно понять, где какое применять и что у них общего с суффиксным массивом.
2 ответа
Все три — способы компактно представить все подстроки строки.
Суффиксный автомат (SAM) — минимальный детерминированный автомат, принимающий все суффиксы. У него линейное число состояний (<= 2n-1) и строится онлайн за O(n) (для константного алфавита; иначе O(n log Σ)). Каждое состояние = класс подстрок с одинаковым множеством позиций окончания (endpos). Силён для: число различных подстрок, наибольшая общая подстрока двух строк, число вхождений каждой подстроки, лексикографически k-я подстрока.
Суффиксное дерево — сжатый бор всех суффиксов; то же множество задач, но строится сложнее (Укконен, O(n)) и его реже пишут на контесте из-за громоздкости. SAM по сути — «дуальный» объект и обычно его и берут.
Суффиксный массив + LCP — не дерево, а отсортированный список суффиксов; проще пишется, решает большинство тех же задач за O(n log n), но некоторые вещи (онлайн-добавление, число вхождений) на SAM элегантнее.
Правило на практике: на CP чаще пишут SAM (компактный код, O(n)) или SA+LCP (если уже наизусть). Суффиксное дерево учат для понимания, но руками пишут редко.
Полезная связь: суффиксное дерево строки s ≈ суффиксный автомат перевёрнутой строки rev(s) (точнее, дерево суффиксных ссылок SAM(rev s) изоморфно суффиксному дереву s). Поэтому, зная SAM, вы фактически имеете суффиксное дерево «бесплатно». Это объясняет, почему на контестах суффиксное дерево почти вытеснено автоматом.