Суффиксный автомат
Минимальный ДКА, принимающий множество суффиксов некоторой строки / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Суффиксный автомат?
Кратко изложите эту статью для 10-летнего ребёнка
Су́ффиксный автома́т (англ. suffix automaton, directed acyclic word graph) — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин[⇨].
Суффиксный автомат | |||||||
---|---|---|---|---|---|---|---|
англ. suffix automaton англ. directed acyclic word graph | |||||||
| |||||||
Тип | Индекс подстрок | ||||||
Год изобретения | 1983 | ||||||
Автор | Ансельм Блумер, Джанет Блумер, Анджей Эренфехт[англ.], Дэвид Хаусслер[англ.], Росс Макконнелл | ||||||
Сложность в О-символике | |||||||
|
|||||||
Медиафайлы на Викискладе |
Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата линейно зависит от длины , а также предложили онлайн-алгоритм[англ.] для его построения с линейным временем работы[⇨]. В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями[⇨], а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов и принимает слова, являющиеся суффиксами хотя бы одного из данных[⇨].
С помощью суффиксного автомата можно эффективно решать такие задачи как поиск подстроки в строке, определение наибольшей общей подстроки двух и более строк и другие[⇨].