Перегляд вихідного коду сторінки Суфіксний автомат

{{Картка:Структура даних
| name               = Суфіксний автомат
| type               = [[Індекс підрядків]]
| invented_by        = Ансельм Блумер, Джанет Блумер, Анджей Еренфехт, Девід Хаусслер, Росс Макконнелл
| invented_year      = [[1983]]
| space_avg          = <math>O(n)</math>
| space_worst        = <math>O(n)</math>
}}
[[Файл:Suffix automaton for abbcbc.svg|thumb|250px|right|Суфіксний автомат для <code>abbcbc</code>.]]
'''Су́фіксний автома́т''' ({{lang-en|suffix automaton, directed acyclic word graph}})&nbsp;— [[структура даних]], що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з [[Підрядок|підрядками]] одного рядка. Є [[Детермінований скінченний автомат|детермінованим скінченним автоматом]], який приймає всі суфікси [[Рядок (програмування)|слова]] <math>S=s_1 s_2 \dots s_n</math> і тільки їх, і що має [[Алгоритми мінімізації скінченних автоматів|найменшу можливу]] кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат&nbsp;— це [[орієнтований ациклічний граф]] з виділеною початковою [[Вершина (теорія графів)|вершиною]] і набором «фінальних» вершин, дуги якого позначені [[Символьний тип даних|символами]], такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова <math>S</math> існує [[Шлях (теорія графів)|шлях]] з початкової вершини в деяку фінальну вершину, символи на якому при [[Конкатенація|конкатенації]] утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.

Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата [[Лінійна функція|лінійно]] залежить від довжини <math>S</math>, а також запропонували [[онлайн алгоритм]] для його побудови з [[Обчислювальна складність|лінійним часом роботи]]. У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з [[Суфіксне дерево|суфікснимі деревами]], а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до [[Префіксне дерево|префіксного дерева]] для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів <math>S_1, S_2, \dots, S_k</math> і приймає слова, які є суфіксами хоча б одного з цих.

За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як [[Алгоритм пошуку рядка|пошук підрядка в рядку]], визначення [[Найдовший спільний підрядок|найдовшого спільного підрядка]] двох і більше рядків тощо.

== Застосування ==
Суфіксний автомат рядка <math>S</math> може використовуватися для розв'язання таких задач, як<ref name=":4">{{Sfn-текст|Crochemore, Hancart|1997|pp=39—41}}</ref><ref>{{Sfn-текст|Crochemore, Hancart|1997|pp=36—39|loc=}}</ref>:

* Підрахунок кількості різних підрядків <math>S</math> за час <math>O(|S|)</math> в режимі онлайн,
* Пошук найдовшого підрядка <math>S</math>, що входить в неї хоча б два рази, за час <math>O(|S|)</math>,
* Пошук [[Найдовший спільний підрядок|найдовшого спільного підрядка]] рядків <math>S</math> і <math>T</math> за час <math>O(|T|)</math>,
* Підрахунок кількості входжень рядка <math>T</math> в <math>S</math> в якості підрядка за час <math>O(|T|)</math>,
* Пошук всіх входжень <math>T</math> в <math>S</math> за час <math>O(|T|+k)</math>, де <math>k</math>&nbsp;— кількість входжень.

Тут варто вважати, що деякий рядок <math>T</math> подається на вхід, коли автомат вже побудований і готовий до використання.

Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних<ref>{{sfn-текст|Yamamoto et al.|2014|loc=|p=675}}</ref>, ідентифікація музики із записаних фрагментів<ref>{{sfn-текст|Crochemore et al.|2003|loc=|p=211}}</ref><ref>{{sfn-текст|Mohri et al.|2009|loc=|страницы=|p=3553}}</ref> і зіставлення геномних послідовностей<ref>{{sfn-текст|Faro|2016|loc=|p=145}}</ref>.

== Примітки ==
{{reflist}}

== Література ==
{{refbegin|2}}
* {{#invoke:Sources|renderSource|Q99428232|ref=Sgarbas et al.}}
* {{#invoke:Sources|renderSource|Q99428342|ref=Perrin}}
* {{#invoke:Sources|renderSource|Q29541479|ref=Weiner}}
* {{#invoke:Sources|renderSource|Q90300966|ref=Pratt}}
* {{#invoke:Sources|renderSource|Q90305414|ref=Slisenko}}
* {{#invoke:Sources|renderSource|Q90309073|ref=Blumer et al.}}
* {{#invoke:Sources|renderSource|Q90311855|ref=Blumer et al.}}
* {{#invoke:Sources|renderSource|Q90327976|ref=Blumer}}
* {{#invoke:Sources|renderSource|Q90329833|ref=Chen, Seiferas}}
* {{#invoke:Sources|renderSource|Q90335534|ref=Inenaga}}
* {{#invoke:Sources|renderSource|Q57518591|ref=Inenaga et al.}}
* {{#invoke:Sources|renderSource|Q90341606|ref=Inenaga et al.}}
* {{#invoke:Sources|renderSource|Q90345535|ref=Inenaga et al.}}
* {{#invoke:Sources|renderSource|Q90348192|ref=Yamamoto et al.}}
* {{#invoke:Sources|renderSource|Q90410044|ref=Fujishige et al.}}
* {{#invoke:Sources|renderSource|Q90410808|ref=Mohri et al.}}
* {{#invoke:Sources|renderSource|Q90412338|ref=Faro}}
* {{#invoke:Sources|renderSource|Q90413384|ref=Crochemore, Hancart}}
* {{#invoke:Sources|renderSource|Q90413885|ref=Crochemore, Vérin}}
* {{#invoke:Sources|renderSource|Q90414195|ref=Crochemore et al.}}
* {{#invoke:Sources|renderSource|Q90418603|ref=Hopcroft, Ullman}}
* {{#invoke:Sources|renderSource|Q90425560|ref=Fiala, Greene}}
* {{#invoke:Sources|renderSource|Q90426624|ref=Senft, Dvořák}}
* {{#invoke:Sources|renderSource|Q90427112|ref=Larsson}}
* {{#invoke:Sources|renderSource|Q90431196|ref=Brodnik, Jekovec}}
* {{#invoke:Sources|renderSource|Q90726647|ref=Rubinchik, Shur}}
* {{#invoke:Sources|renderSource|Q90432456|ref=Серебряков и др.}}
* {{#invoke:Sources|renderSource|Q90435728|ref=Рубцов}}
* {{#invoke:Sources|renderSource|Q90436837|ref=Паращенко}}
{{refend}}

{{Рядки}}

[[Категорія:Рядкові алгоритми]]
[[Категорія:Алгоритми пошуку рядків]]
[[Категорія:Структури даних]]