Суффиксный автомат

Определение:

Суффиксный автомат (англ. suffix automaton, directed acyclic word graph) — минимальный ДКА, который принимает все суффиксы строки и только их.

Описание

Суффиксный автомат [math]A[/math] для строки [math]s[/math] представляет собой ациклический ориентированный граф, с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами [math]s[/math].

Пример суффиксного автомата для строки [math]abbab[/math].

Определение:

Состояние [math]q[/math] принимает строку [math]s[/math], если существует путь из начального состояния в [math]q[/math], такой, что если последовательно выписать буквы на рёбрах на пути, получим строку [math]s[/math].

Определение:

Автомат принимает строку [math]s[/math], если её принимает хотя бы одно из финальных состояний.

Так как автомат детерминированный, то каждому пути соответствует строка.

Если две строки [math]a[/math] и [math]b[/math] принимаются одним состоянием [math]q[/math] произвольного автомата, то для любой строки [math]x[/math] строки [math]ax[/math] и [math]bx[/math] принимаются или не принимаются автоматом одновременно. Действительно, независимо от того, как мы пришли в состояние [math]q[/math], если мы пройдём из него по пути, соответствующему строке [math]x[/math], мы сможем точно сказать, в какое состояние мы попадём (в частности, будет ли оно финальным). Значит, любому состоянию [math]q[/math] соответствует множество строк [math]X_q[/math], которые переводят его в одно из конечных состояний.

Определение:

Множество [math]X_q[/math] называют правым контекстом состояния.

Правый контекст определен не только для состояния, но и для строк, которые оно принимает — правый контекст строк совпадает с правым контекстом состояния.

Утверждение:

Состояний в автомате не меньше, чем различных правых контекстов у подстрок строки, для которой он построен, причём в минимальном автомате достигается нижняя оценка.

[math]\triangleright[/math]

Допустим, что в автомате есть два состояния [math]q_1[/math] и [math]q_2[/math] такие что [math]X_{q_1} = X_{q_2}[/math]. Мы можем удалить состояние [math]q_2[/math] и перевести переходы, ведущие в него в состояние [math]q_1[/math]. Множество принимаемых строк от этого не изменится, следовательно, мы можем продолжать, пока количество состояний не будет равно числу попарно различных правых контекстов.

[math]\triangleleft[/math]

Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны. В случае суффиксного автомата правый контекст [math]X_a[/math] строки [math]a[/math] взаимнооднозначно соответствует множеству правых позиций вхождений строки [math]a[/math] в строку [math]s[/math]. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.

Построение

Определение:

Пусть длина самой короткой строки, которая принимается состоянием [math]q[/math] равно [math]k[/math], тогда суффиксная ссылка [math]link_q[/math] будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.

Будем обозначать длину самой длинной строки, которая принимается состоянием [math]q[/math] как [math]len_q[/math]. Длина самой короткой строки из [math]q[/math] в таком случае будет равна [math]len_{link_q} + 1[/math].

...

Источники информации

• Maxime Crochemore, Christophe Hancart, Thierry Lecroq — Algorithms on Strings
• А. Кульков — Лекция по суффиксным структурам