188
правок
Изменения
м
→Описание
==Описание==
Суффиксный автомат <tex>A</tex> для строки <tex>s</tex> представляет собой [[Основные_определения_теории_графов|ациклический ориентированный граф]], с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>:
* Вершины этого графа {{---}} состояния автомата, а рёбра {{---}} переходы.,* Каждый переход в автомате {{---}} ребро в графе, помеченное некоторым символам. Все рёбра, исходящие из одной вершины имеют разные метки.,* Одно из состояний называется начальным, из него достижимы все остальные состояния. ,
* Одно или несколько состояний помечены как терминальные {{---}} если пройти от начального состояния до терминального по какому-либо пути и выписывать при этом символы на переходах, то получим один из суффиксов строки <tex>s</tex>.
<br>
