Обзор: Суффиксные деревья родственны суффиксным автоматам.
Суффиксные деревья родственны суффиксным автоматам.
Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.
Суффиксное дерево — бор, содержащий все суффиксы некоторой строки. Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.
Теги: Суффиксное дерево Суффиксный автомат деревья