MAXimal

добавлено: 10 Aug 2008 19:50
редактировано: 2 May 2012 22:52

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

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

Например, с помощью суффиксного автомата можно искать все вхождения одной строки в другую, или подсчитывать количество различных подстрок данной строки — обе задачи он позволяет решать за линейное время.

На интуитивном уровне, суффиксный автомат можно понимать как сжатую информацию обо всех подстроках данной строки. Впечатляющим фактом является то, что суффиксный автомат содержит всю информацию в настолько сжатом виде, что для строки длины n он требует лишь O(n) памяти. Более того, он может быть построен также за время O(n) (если мы считаем размер алфавита k константой; в противном случае — за время O (n \log k)).

Исторически, впервые линейность размера суффиксного автомата была открыта в 1983 г. Blumer и др., а в 1985 — 1986 гг. были представлены первые алгоритмы его построения за линейное время (Crochemore, Blumer и др.). Более подробно — см. список литературы в конце статьи.

На английском языке суффиксный автомат называется "suffix automaton" (во множественном числе — "suffix automata"), а ориентированный ациклический граф слов — "directed acyclic word graph" (или просто "DAWG").

Определение суффиксного автомата

Определение. Суффиксным автоматом для данной строки s называется такой минимальный детерминированный конечный автомат, который принимает все суффиксы строки s.

Расшифруем это определение.

  • Суффиксный автомат представляет собой ориентированный ациклический граф, в котором вершины называются состояниями, а дуги графа — это переходы между этими состояниями.

  • Одно из состояний t_0 называется начальным состоянием, и оно должно быть истоком графа (т.е. из него достижимы все остальные состояния).

  • Каждый переход в автомате — это дуга, помеченная некоторым символом. Все переходы, исходящие из какого-либо состояния, обязаны иметь разные метки. (С другой стороны, из состояния может не быть переходов по каким-либо символам.)

  • Одно или несколько состояний помечены как терминальные состояния. Если мы пройдём из начального состояния t_0 по любому пути до какого-либо терминального состояния, и выпишем при этом метки всех пройденных дуг, то получится строка, которая обязана быть одним из суффиксов строки s.

  • Суффиксный автомат содержит минимальное число вершин среди всех автоматов, удовлетворяющих описанным выше условиям. (Минимальность числа переходов не требуется, т.к. при условии минимальности числа состояний в автомате не может быть "лишних" путей — иначе это нарушило бы предыдущее свойство.)

Простейшие свойства суффиксного автомата

Простейшим, и вместе с тем важнейшим свойством суффиксного автомата является то, что он содержит в себе информацию обо всех подстроках строки s. А именно, любой путь из начального состояния t_0, если мы выпишем метки дуг вдоль этого пути, образует обязательно подстроку строки s. И наоборот, любой подстроке строки s соответствует некоторый путь, начинающийся в начальном состоянии t_0.

В целях упрощения объяснений, мы будем говорить, что подстроке соответствует тот путь из начального состояния, метки вдоль которого образуют эту подстроку. И наоборот, мы будем говорить, что любому пути соответствует та строка, которую образуют метки его дуг.

В каждое состояние суффиксного автомата ведёт один или несколько путей из начального состояния. Будем говорить, что состоянию соответствует набор строк, соответствующих всем этим путям.

Примеры построенных суффиксных автоматов

Приведём примеры суффиксных автоматов, построенных для нескольких простых строк.

Начальное состояние мы будем обозначать здесь через t0, а терминальные состояния — отмечать звёздочкой.

Для строки s = :

Для строки s = :

Для строки s = :

Для строки s = :

Для строки s = :

Для строки s = :

Для строки s = :

Алгоритм построения суффиксного автомата за линейное время

Перед тем, как перейти непосредственно к описанию алгоритма построения, надо ввести несколько новых понятий и доказать простые, но очень важные для понимания суффиксного автомата леммы.

Позиции окончаний endpos, их свойства и связь с суффиксным автоматом

Рассмотрим любую непустую подстроку t строки s. Тогда назовём множеством окончаний endpos(t) множество всех позиций в строке s, в которых оканчиваются вхождения строки t.

Мы будем называть две подстроки t_1 и t_2 endpos-эквивалентными, если их множества окончаний совпадают: endpos(t_1) = endpos(t_2). Таким образом, все непустые подстроки строки s можно разбить на несколько классов эквивалентности соответственно их множествам endpos.

Оказывается, что в суффиксном автомате endpos-эквивалентным подстрокам соответствует одно и то же состояние. Иными словами, число состояний в суффиксном автомате равно количеству классов endpos-эквивалентности среди всех подстрок, плюс одно начальное состояние. Каждому состоянию суффиксного автомата соответствуют одна или несколько подстрок, имеющих одно и то же значение endpos.

Это утверждение мы примем как аксиому, и опишем алгоритм построения суффиксного автомата, исходя из этого предположения — как мы затем увидим, все требуемые свойства суффиксного автомата, кроме минимальности, будут выполнены. (А минимальность следует из теоремы Nerode — см. список литературы.)

Приведём также несколько простых, но важных утверждений касательно значений endpos.

Лемма 1. Две непустые подстроки u и w (length(u) \le length(w)) являются endpos-эквивалентными тогда и только тогда, когда строка u встречается в строке s только в виде суффикса строки w.

Доказательство практически очевидно. В одну сторону: если u и w имеют одинаковые позиции окончаний вхождения, то u является суффиксом w, и она присутствует в s только в виде суффикса w. В обратную сторону: если u является суффиксом w и входит только как этот суффикс, то их значения endpos равны по определению.

Лемма 2. Рассмотрим две непустые подстроки u и w (length(u) \le length(w)). Тогда их множества endpos либо не пересекаются, либо endpos(w) целиком содержится в endpos(u), причём это зависит от того, является u суффиксом w или нет:

\begin{cases} endpos(w) \subset endpos(u) & \tex[...]

Доказательство. Предположим, что множества endpos(u) и endpos(w) имеют хотя бы один общий элемент. Тогда это означает, что строки u и w оканчиваются в одном и том же месте, т.е. u — суффикс w. Но тогда каждое вхождение строки w содержит на своём конце вхождение строки u, что и означает, что его множество endpos(w) целиком вкладывается в множество endpos(u).

Лемма 3. Рассмотрим некоторый класс endpos-эквивалентности. Отсортируем все подстроки, входящие в этот класс, по невозрастанию длины. Тогда в получившейся последовательности каждая подстрока будет на единицу короче предыдущей, и при этом являться суффиксом предыдущей. Иными словами, подстроки, входящие в один класс эквивалентности, на самом деле являются суффиксами друг друга, и принимают всевозможные различные длины в некотором отрезке [x;y].

Доказательство.

Зафиксируем некоторый класс endpos-эквивалентности. Если он содержит только одну строку, то корректность леммы очевидна. Пусть теперь количество строк больше одной.

Согласно лемме 1, две различные endpos-эквивалентные строки всегда таковы, что одна является собственным суффиксом другой. Следовательно, в одном классе endpos-эквивалентности не может быть строк одинаковой длины.

Обозначим через w длиннейшую, а через u — кратчайшую строку в данном классе эквивалентности. Согласно лемме 1, строка u является собственным суффиксом строки w. Рассмотрим теперь любой суффикс строки w с длиной в отрезке [length(u); length(w)], и покажем, что он содержится в этом же классе эквивалентности. В самом деле, этот суффикс может входить в s только в виде суффикса строки w (поскольку более короткий суффикс u входит только в виде суффикса строки w). Следовательно, согласно лемме 1, этот суффикс endpos-эквивалентен строке w, что и требовалось доказать.

Суффиксные ссылки

Рассмотрим некоторое состояние автомата v \ne t_0. Как мы теперь знаем, состоянию v соответствует некоторый класс строк с одинаковыми значениями endpos, причём если мы обозначим через w длиннейшую из этих строк, то все остальные будут суффиксами w.

Также мы знаем, что первые несколько суффиксов строки w (если мы рассматриваем суффиксы в порядке убывания их длины) содержатся в том же самом классе эквивалентности, а все остальные суффиксы (как минимум, пустой суффикс) — в каких-то других классах. Обозначим через t первый такой суффикс — в него мы и проведём суффиксную ссылку.

Иными словами, суффиксная ссылка link(v) ведёт в такое состояние, которому соответствует наидлиннейший суффикс строки w, находящийся в другом классе endpos-эквивалентности.

Здесь мы считаем, что начальному состоянию t_0 соответствует отдельный класс эквивалентности (содержащий только пустую строку), и полагаем endpos(t_0) = [-1 \ldots length(s)-1].

Лемма 4. Суффиксные ссылки образуют дерево, корнем которого является начальное состояние t_0.

Доказательство. Рассмотрим произвольное состояние v \ne t_0. Суффиксная ссылка link(v) ведёт из него в состояние, которому соответствуют строки строго меньшей длины (это следует из определения суффиксной ссылки и из леммы 3). Следовательно, двигаясь по суффиксным ссылкам, мы рано или поздно придём из состояния v в начальное состояние t_0, которому соответствует пустая строка.

Лемма 5. Если мы построим из всех имеющихся множеств endpos дерево (по принципу "множество-родитель содержит как подмножества всех своих детей"), то оно будет совпадать по структуре с деревом суффиксных ссылок.

Доказательство.

То, что из множеств endpos можно построить дерево, следует из леммы 2 (о том, что любые два множества endpos либо не пересекаются, либо одно содержится в другом).

Рассмотрим теперь произвольное состояние v \ne t_0 и его суффиксную ссылку link(v). Из определения суффиксной ссылки и из леммы 2 следует:

endpos(v) \subset endpos(link(v)),

что вкупе с предыдущей леммой и доказывает наше утверждение: дерево суффиксных ссылок по сути своей есть дерево вкладывающихся множеств endpos.

Приведём пример дерева суффиксных ссылок в суффиксном автомате, построенном для строки :

Промежуточный итог

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

  • Множество подстрок строки s можно разбить на классы эквивалентности согласно их множествам окончания endpos.

  • Суффиксный автомат состоит из начального состояния t_0, а также по одному состоянию на каждый класс endpos-эквивалентности.

  • Каждому состоянию v соответствует одна или несколько строк. Обозначим через longest(v) длиннейшую из таких строк, через len(v) её длину. Обозначим через shortest(v) кратчайшую из таких строк, а её длину через minlen(v).

    Тогда все строки, соответствующие этому состоянию, являются различными суффиксами строки longest(v) и имеют всевозможные длины в отрезке [minlen(v); len(v)].

  • Для каждого состояния v \ne t_0 определена суффиксная ссылка, ведущая в такое состояние, которое соответствует суффиксу строки longest(v) длины minlen(v)-1. Суффиксные ссылки образуют дерево с корнем в t_0, причём это дерево, по сути, является деревом отношений включения между множествами endpos.

  • Таким образом, minlen(v) для v \ne t_0 выражается с помощью суффиксной ссылки link(v) как:

    minlen(v) = len(link(v)) + 1.

  • Если мы стартуем из произвольного состояния v_0 и будем идти по суффиксным ссылкам, то рано или поздно дойдём до начального состояния t_0. При этом у нас получится последовательность непересекающихся отрезков [minlen(v_i); len(v_i)], которые в объединении дадут один сплошной отрезок.

Алгоритм построения суффиксного автомата за линейное время

Приступим к описанию самого алгоритма. Алгоритм будет онлайновым, т.е. будет добавлять по одному символу строки s, перестраивая соответствующим образом текущий автомат.

Чтобы достичь линейного потребления памяти, в каждом состоянии мы будем хранить только значение len, link и список переходов из этого состояния. Метки терминальных состояний мы поддерживать не будем (мы покажем, как расставить эти метки после построения суффиксного автомата, если имеется необходимость в них).

Изначально автомат состоит из единственного состояния t_0, которое мы условимся считать нулевым состоянием (остальные состояния будут получать номера 1, 2, \ldots). Присвоим этому состоянию len = 0, а значению link присвоим для удобства -1 (означающее ссылку на фиктивное, несуществующее состояние).

Соответственно, вся задача теперь сводится к тому, чтобы реализовать обработку добавления одного символа c в конец текущей строки. Опишем этот процесс:

  • Пусть last — это состояние, соответствующее всей текущей строке до добавления символа c. (Изначально last = 0, а после добавления каждого символа мы будем менять значение last.)

  • Создадим новое состояние cur, проставив ему len(cur) = len(last) + 1. Значение link(cur) пока считаем неопределённым.

  • Сделаем такой цикл: изначально мы стоим в состоянии last; если из него нет перехода по букве c, то добавляем этот переход по букве c в состояние cur, и затем переходим по суффиксной ссылке, снова проверяя — если нет перехода, то добавляем. Если в какой-то момент случится, что такой переход уже есть, то останавливаемся — и обозначим через p номер состояния, на котором это произошло.

  • Если ни разу не случилось, что переход по букве c уже имелся, и мы так и дошли до фиктивного состояния -1 (в которое мы попали по суффиксной ссылке из начального состояния t_0), то мы можем просто присвоить link(cur) = 0 и выйти.

  • Допустим теперь, что мы остановились на некотором состоянии p, из которого уже был переход по букве c. Обозначим через q то состояние, куда ведёт этот имеющийся переход.

  • Теперь у нас два случая в зависимости от того, len(p) + 1 = len(q) или нет.

  • Если len(p) + 1 = len(q), то мы можем просто присвоить link(cur) = q и выйти.

  • В противном случае, всё несколько сложнее. Необходимо произвести "клонирование" состояния q: создать новое состояние clone, скопировав в него все данные из вершины q (суффиксную ссылку, переходы), за исключением значения len: надо присвоить len(clone) = len(p) + 1.

    После клонирования мы проводим суффиксную ссылку из cur в это состояние clone, также перенаправляем суффиксную ссылку из q в clone.

    Наконец, последнее, что мы должны сделать — это пройтись от состояния p по суффиксным ссылкам, и для каждого очередного состояния проверять: если имелся переход по букве c в состояние q, то перенаправлять его в состояние clone (а если нет, то останавливаться).

  • В любом случае, чем бы ни закончилось выполнение этой процедуры, мы в конце обновляем значение last, присваивая ему cur.

Если нам также нужно знать, какие вершины являются терминальными, а какие — нет, то мы можем найти все терминальные вершины после построения суффиксного автомата для всей строки. Для этого рассмотрим состояние, соответствующее всей строке (оно, очевидно, у нас сохранено в переменной last), и будем идти по его суффиксным ссылкам, пока не дойдём до начального состояния, и помечать каждое пройденное состояние как терминальное. Легко понять, что тем самым мы пометим состояния, соответствующие всем суффиксам строки s, что нам и требовалось.

В следующем разделе мы подробно рассмотрим каждый шаг алгоритма и покажем его корректность.

Здесь же лишь отметим, что из алгоритма видно, что добавление одного символа приводит к добавлению одного или двух состояний в автомат. Таким образом, линейность числа состояний очевидна.

Линейность числа переходов, да и вообще линейное время работы алгоритма менее понятны, и они будут доказаны ниже, после доказательства корректности алгоритма.

Доказательство корректности алгоритма

  • Назовём переход (p,q) сплошным, если len(p) + 1 = len(q). В противном случае, т.е. когда len(p) + 1 < len(q), переход будем называть несплошным.

    Как можно увидеть из описания алгоритма, сплошные и несплошные переходы приводят к разным ветвям алгоритма. Сплошные переходы называются так потому, что, появившись впервые, они больше никогда не будут меняться. В противоположность им, несплошные переходы могут измениться при добавлении новых букв к строке (измениться может конец дуги-перехода).

  • Во избежание неоднозначностей, под строкой s мы будем подразумевать строку, для которой был построен суффиксный автомат до добавления текущего символа c.

  • Алгоритм начинается с того, что мы создаём новое состояние cur, которому будет соответствовать вся строка s + c. Понятно, почему мы обязаны создать новое состояние — т.к. вместе с добавлением нового символа возникает новый класс эквивалентности — это класс строк, оканчивающихся на добавляемом символе c.

  • После создания нового состояния алгоритм проходится по суффиксным ссылкам, начиная с состояния, соответствующего всей строке s, и пытается добавить переход по символу c в состояние cur. Тем самым, мы приписываем к каждому суффиксу строки s символ c. Но добавлять новые переходы мы можем только в том случае, если они не будут конфликтовать с уже имеющимися, поэтому, как только мы встретим уже имеющийся переход по символу c, мы сразу же обязаны остановиться.

  • Самый простой случай — если мы так и дошли до фиктивного состояния -1, добавив везде по новому переходу вдоль символа c. Это означает, что символ c в строке s ранее не встречался. Мы успешно добавили все переходы, осталось только проставить суффиксную ссылку у состояния cur — она, очевидно, должна быть равна 0, поскольку состоянию cur в данном случае соответствуют все суффиксы строки s+c.

  • Второй случай — когда мы наткнулись на уже имеющийся переход (p,q). Это означает, что мы пытались добавить в автомат строку x+c (где x — некоторый суффикс строки s, имеющий длину len(p)), а эта строка уже была ранее добавлена в автомат (т.е. строка x+c уже входит как подстрока в строку s). Поскольку мы предполагаем, что автомат для строки s построен корректно, то новых переходов мы больше добавлять не должны.

    Однако возникает сложность с тем, куда вести суффиксную ссылку из состояния cur. Нам требуется провести суффиксную ссылку в такое состояние, в котором длиннейшей строкой будет являться как раз эта самая x+c, т.е. len для этого состояния должен быть равен len(p) + 1. Однако такого состояния могло и не существовать: в таком случае нам надо произвести "расщепление" состояния.

  • Итак, по одному из возможных сценариев, переход (p,q) оказался сплошным, т.е. len(q) = len(p) + 1. В этом случае всё просто, никакого расщепления производить не надо, и мы просто проводим суффиксную ссылку из состояния cur в состояние q.

  • Другой, более сложный вариант — когда переход несплошной, т.е. len(q) > len(p) + 1. Это означает, что состоянию q соответствует не только нужная нам подстрока w+c длины len(p) + 1, но также и подстроки большей длины. Нам ничего не остаётся, кроме как произвести "расщепление" состояния q: разбить отрезок строк, соответствующих ей, на два подотрезка, так что первый будет заканчиваться как раз длиной len(p) + 1.

    Как производить это расщепление? Мы "клонируем" состояние q, делая его копию clone с параметром len(clone) = len(p) + 1. Мы копируем в clone из q все переходы, поскольку мы не хотим никоим образом менять пути, проходившие через q. Суффиксную ссылку из clone мы ведём туда, куда вела старая суффиксная ссылка из q, а ссылку из q направляем в clone.

    После клонирования мы проводим суффиксную ссылку из cur в clone — то, ради чего мы и производили клонирование.

    Остался последний шаг — перенаправить некоторые входящие в q переходы, перенаправив их на clone. Какие именно входящие переходы надо перенаправить? Достаточно перенаправить только переходы, соответствующие всем суффиксам строки w+c, т.е. нам надо продолжить двигаться по суффиксным ссылкам, начиная с вершины p, и до тех пор, пока мы не дойдём до фиктивного состояния -1 или не дойдём до состояния, переход из которого ведёт в состояние, отличное от q.

Доказательство линейного числа операций

Во-первых, сразу оговоримся, что мы считаем размер алфавита константой. Если это не так, то говорить о линейном времени работы не получится: список переходов из одной вершины надо хранить в виде сбалансированного дерева, позволяющего быстро производить операции поиска по ключу и добавления ключа. Следовательно, если мы обозначим через k размер алфавита, то асимптотика алгоритма составит O (n \log k) при O (n) памяти. Впрочем, если алфавит достаточно мал, то можно, пожертвовав памятью, избежать сбалансированных списков, а хранить переходы в каждой вершине в виде массива длины k (для быстрого поиска по ключу) и динамического списка (для быстрого обхода всех имеющихся ключей). Тем самым мы достигнем O(n) во времени работы алгоритма, но ценой O (n k) потребления памяти.

Итак, мы будем считать размер алфавита константным, т.е. каждая операция поиска перехода по символу, добавления перехода, поиск следующего перехода — все эти операции мы считаем работающими за O(1).

Если мы рассмотрим все части алгоритма, то он содержит три места, линейная асимптотика которых не очевидна:

  • Первое место — это проход по суффиксным ссылкам от состояния last с добавлением рёбер по символу c.

  • Второе место — копирование переходов при клонировании состояния q в новое состояние clone.

  • Третье место — перенаправление переходов, ведущих в q, на clone.

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

Тогда очевидна линейная суммарная асимптотика первого и второго места: ведь каждая операция здесь добавляет в автомат один новый переход.

Осталось оценить суммарную асимптотику в третьем месте — в том, где мы перенаправляем переходы, ведущие в q, на clone. Обозначим v = longest(p). Это суффикс строки s, и с каждой итерацией его длина убывает — а, значит, и позиция v как суффикса строки s монотонно возрастает с каждой итерацией. При этом, если перед первой итерацией цикла соответствующая строка v была на глубине k (k \ge 2) от last (если считать глубиной число суффиксных ссылок, которые надо пройти), то после последней итерации строка v+c станет 2-ой суффиксной ссылкой на пути от cur (которое станет новым значением last).

Таким образом, каждая итерация этого цикла приводит к тому, что позиция строки longest(link(link(last)) как суффикса всей текущей строки будет монотонно увеличиваться. Следовательно, всего этот цикл не мог отработать более n итераций, что и требовалось доказать.

(Стоит заметить, что аналогичные аргументы можно использовать и для доказательства линейности работы первого места, вместо ссылки на доказательство линейности числа состояний.)

Реализация алгоритма

Вначале опишем структуру данных, которая будет хранить всю информацию о конкретном переходе (len, link, список переходов). При необходимости сюда можно добавить флаг терминальности, а также другую требуемую информацию. Список переходов мы храним в виде стандартного контейнера map, что позволяет достичь суммарно O(n) памяти и O (n \log k) времени на обработку всей строки.

struct state {
	int len, link;
	map<char,int> next;
};

Сам суффиксный автомат будем хранить в виде массива этих структур state. Как доказывается в следующем разделе, если MAXN — это максимально возможная в программе длина строки, то достаточно завести память под 2 \cdot MAXN - 1 состояний. Также мы храним переменную last — состояние, соответствующее всей строке на данный момент.

const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;

Приведём функцию, инициализирующую суффиксный автомат (создающую автомат с единственным начальным состоянием):

void sa_init() {
	sz = last = 0;
	st[0].len = 0;
	st[0].link = -1;
	++sz;
	/*
	// этот код нужен, только если автомат строится много раз для разных строк:
	for (int i=0; i<MAXLEN*2; ++i)
		st[i].next.clear();
	*/
}

Наконец, приведём реализацию основной функции — которая добавляет очередной символ в конец текущей строки, перестраивая соответствующим образом автомат:

void sa_extend (char c) {
	int cur = sz++;
	st[cur].len = st[last].len + 1;
	int p;
	for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
		st[p].next[c] = cur;
	if (p == -1)
		st[cur].link = 0;
	else {
		int q = st[p].next[c];
		if (st[p].len + 1 == st[q].len)
			st[cur].link = q;
		else {
			int clone = sz++;
			st[clone].len = st[p].len + 1;
			st[clone].next = st[q].next;
			st[clone].link = st[q].link;
			for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
				st[p].next[c] = clone;
			st[q].link = st[cur].link = clone;
		}
	}
	last = cur;
}

Как уже упоминалось выше, если пожертвовать памятью (до O (n k), где k — размер алфавита), то можно достичь времени построения автомата O (n) даже для любых k — но для этого придётся в каждом состоянии хранить массив размера k (для быстрого поиска перехода по нужной букве) и список всех переходов (для быстрого обхода или копирования всех переходов).

Дополнительные свойства суффиксного автомата

Число состояний

Число состояний в суффиксном автомате, построенном для строки s длины n, не превышает 2n-1 (для n \ge 3).

Доказательством этого является описанный выше алгоритм (поскольку изначально автомат состоит из одного начального состояния, на первом и втором шагах добавляется ровно по одному состоянию, а на каждом из остальных n-2 шагах могло добавляться по две вершины из-за расщепления состояния).

Однако эту оценку легко показать и без знания алгоритма. Вспомним о том, что число состояний равно количеству различных значений множеств endpos. Кроме того, эти множества endpos образуют дерево по принципу "вершина-родитель содержит в себе как подмножества всех детей". Рассмотрим это дерево, и немного преобразуем его: пока в нём есть внутренняя вершина с одним сыном, то это означает, что endpos этого сына не содержит как минимум одно число из endpos родителя; тогда создадим виртуальную вершину с endpos, равным этому числу, и привесим этого сына к родителю. В итоге мы получим дерево, в котором каждая внутренняя вершина имеет степень больше единицы, а число листьев не превосходит n. Следовательно, всего в таком дереве не более 2n-1 вершины.

Итак, мы показали эту оценку независимо, без знания алгоритма.

Интересно заметить, что эта оценка неулучшаема, т.е. существует тест, на котором она достигается. Этот тест выглядит таким образом:

При обработке этой строки на каждой итерации, начиная с третьей, будет происходить расщепление состояния, и, тем самым, будет достигаться оценка 2n-1.

Число переходов

Число переходов в суффиксном автомате, построенном для строки s длины n, не превышает 3n-4 (для n \ge 3).

Докажем это.

Оценим число сплошных переходов. Рассмотрим остовное дерево из длиннейших путей в автомате, начинающихся в состоянии t_0. Этот остов будет состоять только из сплошных рёбер, а, значит, их количество на единицу меньше числа состояний, т.е. не превосходит 2n-2.

Оценим теперь число несплошных переходов. Рассмотрим каждый несплошной переход; пусть текущий переход — это переход (p,q) по символу c. Поставим ему в соответствие строку u+c+w, где строка u соответствует длиннейшему пути из начального состояния в p, а w — длиннейшему пути из q в какое-либо терминальное состояние. С одной стороны, все такие строки u+c+w для всех несплошных переходов будут различными (поскольку строки u и w образованы только сплошными переходами). С другой стороны, каждая из таких строк u+c+w, по определению терминального состояния, будет суффиксом всей строки s. Поскольку непустых суффиксов у строки s всего n штук, и к тому же вся строка s среди этих строк u+c+w не могла содержаться (т.к. всей строке s соответствует путь из n сплошных рёбер), то общее число несплошных переходов не превосходит n-1.

Складывая эти две оценки, мы получаем оценку 3n-3. Однако, вспоминая, что максимальное число состояний достигается только на тесте вида , и на нём оценка 3n-3 явно не достигается, получаем окончательную оценку 3n-4, что и требовалось доказать.

Интересно отметить, что также существует тест, на котором эта оценка достигается:

Связь с суффиксным деревом. Построение суффиксного дерева по суффиксному автомату и наоборот

Докажем две теоремы, устанавливающие взаимную связь между суффиксным автоматом и суффиксным деревом.

Сразу оговоримся, что мы считаем, что входная строка такова, что каждый суффикс имеет собственную вершину в суффиксном дереве (поскольку для произвольных строк это, вообще говоря, неверно: например, для строки ). Обычно этого добиваются путём приписывания в конец строки какого-нибудь особого символа (обычно обозначаемого через знак доллара).

Для удобства введём обозначения: \overline{s} — это строка s, записанная в обратном порядке, DAWG(s) — это суффиксный автомат, построенный для строки s, ST(s) — это суффиксное дерево строки s.

Введём понятие расширяющей ссылки: зафиксируем вершину суффиксного дерева v и символ c; тогда расширяющая ссылка ext[c,v] ведёт в вершину дерева, соответствующую строке c+v (если этот путь c+v оканчивается посередине ребра, то проведём ссылку в нижний конец этого ребра); если такого пути c+v вообще нет в дереве, то расширяющая ссылка не определена. В некотором смысле, расширяющие ссылки противоположны суффиксным ссылкам.

Теорема 1. Дерево, образованное суффиксными ссылками в DAWG(s), является суффиксным деревом ST(\overline{s}).

Теорема 2. DAWG(s) — это граф расширяющих ссылок суффиксного дерева ST(\overline{s}). Кроме того, сплошные рёбра в DAWG(s) — это инвертированные суффиксные ссылки в ST(\overline{s}).

Эти две теоремы позволяют по одной из структур (суффиксному дереву или суффиксному автомату) построить другую за время O(n) — эти два простых алгоритма будут рассмотрены нами ниже в теоремах 3 и 4.

В целях наглядности, приведём суффиксный автомат с его деревом суффиксных ссылок и соответствующее суффиксное дерево для инвертированной строки. Для примера возьмём строку s = .

DAWG( и его дерево суффиксных ссылок (для наглядности мы подписываем каждое состояние его longest-строкой):

ST(:

Лемма. Следующие три утверждения эквивалентны для любых двух подстрок u и w:

  • endpos(u) = endpos(w) в строке s
  • firstpos(\overline{u}) = firstpos(\overline{w}) в строке \overline{s}
  • \overline{u} и \overline{w} лежат на одном и том же пути из корня в суффиксном дереве ST(\overline{s}).

Доказательство её довольно очевидно: если начала вхождений двух строк совпадают, то одна строка является префиксом другой, а, значит, одна строка лежит в суффиксном дереве на пути другой строки.

Доказательство теоремы 1.

Состояния суффиксного автомата соответствуют вершинам суффиксного дерева.

Рассмотрим произвольную суффиксную ссылку y = link(x). Согласно определению суффиксной ссылки, longest(y) является суффиксом longest(x), причём среди всех таких y выбирается тот, у которого len(y) максимально.

В терминах инвертированной строки \overline{s} это означает, что суффиксная ссылка link[x] ведёт в такой длиннейший префикс строки, соответствующей состоянию x, чтобы этому префиксу соответствовало отдельное состояние y. Иными словами, суффиксная ссылка link[x] ведёт в предка вершины x в суффиксном дереве, что и требовалось доказать.

Доказательство теоремы 2.

Состояния суффиксного автомата соответствуют вершинам суффиксного дерева.

Рассмотрим произвольный переход (x,y,c) в суффиксном автомате DAWG(s). Наличие этого перехода означает, что y — это такое состояние, класс эквивалентности которого содержит подстроку longest(x) + c. В инвертированной строке \overline{s} это означает, что y это такое состояние, которому соответствует подстрока, firstpos от которой (в тексте \overline{s}) совпадает с firstpos от подстроки c + \overline{longest(x)}.

Это как раз и означает, что:

\overline{longest(y)} = ext[c, \overline{longest([...]

Первая часть теоремы доказана, осталось доказать вторую часть: что все сплошные переходы в автомате соответствуют суффиксным ссылкам в дереве. Сплошной переход отличается от несплошного тем, что length(y) = length(x) + 1, т.е. после приписывания символа c мы попали в состояние со строкой, максимальной из класса эквивалентности этого состояния. Это означает, что при вычислении соответствующей расширяющей ссылки ext[c, \overline{longest(x)}] мы сразу попали в вершину дерева, а не спускались вниз до ближайшей вершины дерева. Таким образом, приписав один символ в начало, мы попали в другую вершину дерева — значит, если это и есть инвертированная суффиксная ссылка в дереве.

Теорема полностью доказана.

Теорема 3. Имея суффиксный автомат DAWG(s), можно за время O(n) построить суффиксное дерево ST(\overline{s}).

Теорема 4. Имея суффиксное дерево ST(\overline{s}), можно за время O(n) построить суффиксный автомат DAWG(s).

Доказательство теоремы 3.

Суффиксное дерево ST(\overline{s}) будет содержать столько же вершин, сколько состояний в DAWG(s), причём вершине дерева, получившейся из состояния v автомата, соответствует строка длины len(v).

Согласно теореме 1, рёбра в дереве образуются как инвертированные суффиксные ссылки, и дуговые метки можно найти, исходя из разности len состояний, и дополнительно зная для каждого состояния автомата один любой элемент его множества endpos (этот один элемент множества endpos можно поддерживать при построении автомата).

Суффиксные ссылки в дереве мы можем построить согласно теореме 2: для этого достаточно просмотреть все сплошные переходы в автомате, и для каждого такого перехода (x,y) добавить ссылку link(y) = x.

Таким образом, за время O(n) мы можем построить суффиксное дерево вместе с суффиксными ссылками в нём.

(Если мы считаем размер k алфавита не константой, то на всё перестроение потребуется время O (n \log k).)

Доказательство теоремы 4.

Суффиксный автомат DAWG(s) будет содержать столько же состояний, сколько вершин в ST(\overline{s}). У каждого состояния v его длиннейшая строка longest(v) будет соответствовать инвертированному пути из корня дерева до вершины v.

Согласно теореме 2, чтобы построить все переходы в суффиксном автомате, нам надо найти все расширяющие ссылки ext[c,v].

Во-первых, заметим, что часть этих расширяющих ссылок получаются непосредственно из суффиксных ссылок в дереве. В самом деле, если для любой вершины x мы рассмотрим её суффиксную ссылку y = link(x), то это означает, что надо провести расширяющую ссылку из y в x по первому символу строки, соответствующей вершине x.

Однако так мы найдём не все расширяющие ссылки. Дополнительно надо пройтись по суффиксному дереву от листьев до корня, и для каждой вершины v просмотреть всех её сыновей, для каждого сына просмотреть все расширяющие ссылки ext[c,w], и скопировать эту ссылку в вершину v, если по этому символу c ссылка из вершины v ещё не была найдена:

ext[c,v] = ext[c,w], ~~~~ \text{if $ext[c,w] = ni[...]

Этот процесс отработает за время O (n), если мы считаем размер алфавита константным.

Наконец, осталось построить суффиксные ссылки в автомате, однако, согласно теореме 1, эти суффиксные ссылки получаются просто как рёбра суффиксного дерева ST(\overline{s}).

Таким образом, описанный алгоритм за время O(n) строит суффиксный автомат по суффиксному дереву для инвертированной строки.

(Если же мы считаем, что размер k алфавита — также переменная величина, то асимптотика увеличится до O (n \log k).)

Применения при решении задач

Ниже мы рассмотрим, какие задачи можно решать с помощью суффиксного автомата.

Мы для простоты будем считать размер алфавита k константой, что позволит нам считать асимптотику построения суффиксного автомата и прохода по нему константными.

Проверка вхождения

Условие. Дан текст T, и поступают запросы в виде: дана строка P, требуется проверить, входит или нет строка P в текст T как подстрока.

Асимптотика. Препроцессинг O (length (T)) и O (length (P)) на один запрос.

Решение. Построим суффиксный автомат по тексту T за время O (length (T)).

Как теперь отвечать на один запрос. Пусть текущее состояние — это переменная v, изначально она равна начальному состоянию t_0. Будем идти по символам строки P, соответствующим образом делая переход из текущего состояния v в новое состояние. Если в какой-то момент случилось, что перехода из текущего состояния по нужному символу не оказалось — то ответ на запрос "нет". Если же мы смогли обработать всю строку P, то ответ на запрос "да".

Понятно, что это будет работать за время O (length (P)). Более того, алгоритм фактически ищет длину наидлиннейшего префикса P, встречающегося в тексте — и если входные образцы таковы, что эти длины маленькие, то и алгоритм будет работать значительно быстрее, не обрабатывая всю строку целиком.

Количество различных подстрок

Условие. Дана строка S. Требуется узнать количество различных её подстрок.

Асимптотика. O (length (S)).

Решение. Построим суффиксный автомат по строке S.

В суффиксном автомате любой подстроке строки S соответствует какой-то путь в автомате. Поскольку повторяющихся строк в автомате быть не может, то ответ на задачу — это количество различных путей в автомате, начинающихся в начальной вершине t_0.

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

А именно, пусть d[v] — это количество различных путей, начинающихся с состояния v (включая путь длины ноль). Тогда верно:

d[v] = 1 + \sum_{w ~ : \atop (v,w,c) \in DAWG} d[[...]

т.е. d[v] можно выразить как сумму ответов по всевозможным переходам из состояния v.

Ответом на задачу будет значение d[t_0]-1 (единица отнимается, чтобы не учитывать пустую подстроку).

Суммарная длина различных подстрок

Условие. Дана строка S. Требуется узнать суммарную длину всех различных её подстрок.

Асимптотика. O (length (S)).

Решение. Решение задачи аналогично предыдущей, только теперь надо считать в динамике две величины: количество различных подстрок d[v] и их суммарную длину ans[v].

Как считать d[v], описано в предыдущей задаче, а величину ans[v] можно вычислить таким образом:

ans[v] = \sum_{w ~ : \atop (v,w,c) \in DAWG} d[w][...]

т.е. мы берём ответ для каждой вершины w, и прибавляем к нему d[w], тем самым как бы приписывая в начало каждой из строк по одному символу.

Лексикографически k-ая подстрока

Условие. Дана строка S. Поступают запросы — числа K_i, и требуется находить K_i-ую в порядке сортировки подстроку строки S.

Асимптотика. O (length (ans) \cdot Alphabet) на один запрос (где ans — это ответ на этот запрос, Alphabet — размер алфавита).

Решение. Решение данной задачи базируется на той же идее, что и предыдущие две задачи. Лексикографически k-ая подстрока — это лексикографический k-ый путь в суффиксном автомате. Поэтому посчитав для каждого состояния количество путей из него, мы сможем легко искать k-ый путь, двигаясь от корня автомата.

Наименьший циклический сдвиг

Условие. Дана строка S. Требуется найти лексикографически наименьший её циклический сдвиг.

Асимптотика. O (length (S)).

Решение. Построим суффиксный автомат для строки S+S. Тогда этот автомат будет содержать в себе как пути все циклические сдвиги строки S.

Следовательно, задача сведётся к тому, чтобы найти в автомате лексикографически минимальный путь длины length(S), что делается тривиальным образом: мы стартуем в начальном состоянии и каждый раз действуем жадно, переходя по переходу с минимальным символом.

Количество вхождений

Условие. Дан текст T, и поступают запросы в виде: дана строка P, требуется узнать, сколько раз строка P входит в текст T как подстрока (вхождения могут перекрываться).

Асимптотика. Препроцессинг O (length (T)) и O (length (P)) на один запрос.

Решение. Построим суффиксный автомат по тексту T.

Дальше нам надо сделать такой препроцессинг: для каждого состояния v автомата посчитать число cnt[v], равное размеру множества endpos(v). В самом деле, все строки, соответствующие одному и тому же состоянию, входят в T одинаковое число раз, равное количеству позиций в множестве endpos.

Однако явно поддерживать множества endpos для всех состояний мы не можем, поэтому научимся считать только их размеры cnt.

Для этого поступим следующим образом. Для каждого состояния, если оно не было получено путём клонирования (и начальное состояние t_0 мы также не учитываем), изначально присвоим cnt = 1. Затем будем идти по всем состояниям в порядке убывания их длины len и пробрасывать текущее значение cnt[v] по суффиксной ссылке:

cnt[link(v)] += cnt[v].

Утверждается, что в конце концов мы так посчитаем для каждого состояния правильные значения cnt.

Почему это верно? Всего состояний, полученных не путём клонирования, ровно length(S), и i-ое из них появилось, когда мы добавили первые i символов. Следовательно, каждому из этих состояний мы ставим в соответствие эту позицию, при обработке которой оно появилось. Поэтому изначально у каждого такого состояния cnt = 1, а у всех остальных состояний cnt = 0.

Затем мы выполняем для каждого v такую операцию: cnt[link(v)] += cnt[v]. Смысл этого заключается в том, что если строка, соответствующая состоянию v, встречалась cnt[v] раз, то все её суффиксы будут встречаться столько же.

Почему тем самым мы не учтём одну и ту же позицию несколько раз? Потому что из каждого состояния его значение "пробрасывается" только один раз, поэтому не могло так получиться, что из одного состояния его значение "пробросилось" до какого-то другого состояния дважды, двумя разными путями.

Таким образом, мы научились считать эти величины cnt для всех состояний автомата.

После этого ответ на запрос тривиален — надо просто вернуть cnt[t], где t — состояние, соответствующее образцу P.

Позиция первого вхождения

Условие. Дан текст T, и поступают запросы в виде: дана строка P, требуется узнать позицию начала первого вхождения строки P.

Асимптотика. Препроцессинг O (length (T)) и O (length (P)) на один запрос.

Решение. Построим суффиксный автомат по тексту T.

Для решения задачи нам также надо добавить в препроцессинг нахождение позиций firstpos для всех состояний автомата, т.е. для каждого состояния v мы хотим найти позицию firstpos[v] окончания первого вхождения. Иными словами, мы хотим найти заранее минимальный элемент каждого из множеств endpos(v) (поскольку явно поддерживать все множества endpos мы не можем).

Поддерживать эти позиции firstpos проще всего прямо по ходу построения автомата: когда мы создаём новое состояние cur при входе в функцию sa\_extend(), то выставляем ему:

firstpos(cur) = len(cur) - 1

(если мы работаем в 0-индексации).

При клонировании вершины q в clone мы ставим:

firstpos(clone) = firstpos(q),

(поскольку другой вариант значения только один — это firstpos(cur), что явно больше).

Таким образом, ответ на запрос — это просто firstpos(t)-length(P)+1, где t — состояние, соответствующее образцу P.

Позиции всех вхождений

Условие. Дан текст T, и поступают запросы в виде: дана строка P, требуется вывести позиции всех её вхождений в строку T (вхождения могу перекрываться).

Асимптотика. Препроцессинг O (length (T)). Ответ на один запрос за O (length (P) + answer (P)), где answer(P) — это размер ответа, т.е. мы будем решать задачу за время порядка размера ввода и вывода.

Решение. Построим суффиксный автомат по тексту T. Аналогично предыдущей задаче, посчитаем в процессе построения автомата для каждого состояния позицию firstpos окончания первого вхождения.

Пусть теперь поступил запрос — строка P. Найдём, какому состоянию t она соответствует.

Понятно, что firstpos(t) точно должно входить в ответ. Какие ещё позиции надо найти? Мы учли состояние автомата, содержащее строку P, однако не учли другие состояния, которым соответствуют такие строки, что P является их суффиксом.

Иными словами, нам требуется найти все состояния, из которых достижимо по суффиксным ссылкам состояние t.

Следовательно, для решения задачи нам потребуется сохранить для каждого состояния список суффиксных ссылок, ведущих в него. Ответ на запрос тогда будет заключаться в том, чтобы сделать обход в глубину/в ширину по этим инвертированным суффиксным ссылкам, начиная с состояния t.

Этот обход будет работать за время O (answer (P)), поскольку мы не посетим одно и то же состояние дважды (потому что из каждого состояния суффиксная ссылка выходит только одна, поэтому не может быть двух путей, ведущих в одно и то же состояние).

Правда, надо учитывать, что у двух состояний их значения firstpos могут совпадать: если одно состояние было получено клонированием другого. Однако это не ухудшает асимптотику, поскольку у каждой не-клонированной вершины может быть максимум один клон.

Более того, можно легко избавиться от вывода повторяющихся позиций, если мы не будем добавлять в ответ firstpos от состояний-клонов. В самом деле, в любое состояние-клон ведёт суффиксная ссылка из того первоначального состояния, которое это состояние клонировало. Таким образом, если мы для каждого состояния запомним флаг is\_clon, и не будем добавлять в ответ firstpos от состояний, для которых is\_clon = true, то мы тем самым получим все требуемые answer (P) позиций без повторов.

Приведём наброски реализации:

struct state {
	...
	bool is_clon;
	int first_pos;
	vector<int> inv_link;
};
 
 
... после построения автомата ...
for (int v=1; v<sz; ++v)
	st[st[v].link].inv_link.push_back (v);
...
 
 
// ответ на запрос - вывод всех вхождений (возможно, с повторами)
void output_all_occurences (int v, int P_length) {
	if (! st[v].is_clon)
		cout << st[v].first_pos - P_length + 1 << endl;
	for (size_t i=0; i<st[v].inv_link.size(); ++i)
		output_all_occurences (st[v].inv_link[i], P_length);
}

Поиск кратчайшей строки, не входящей в данную

Условие. Дана строка S, и задан определённый алфавит. Требуется найти такую строку наименьшей длины, что она не встречается в S как подстрока.

Асимптотика. Решение за O (length (S)).

Решение. Решать будет динамическим программирование по автомату, построенному для строки S.

Пусть d[v] — это ответ для вершины v, т.е. мы уже набрали часть подстроки, оказавшись в состоянии v, и хотим найти наименьшее число символов, которое надо ещё добавить, чтобы выйти за пределы автомата, найдя несуществующий переход.

Считается d[v] очень просто. Если из v нет перехода хотя бы по одному символу из алфавита, то d[v] = 1: мы можем приписать такой символ и выйти за пределы автомата, получив тем самым искомую строку.

В противном случае, одним символом обойтись не получится, поэтому надо взять минимум из ответов по всевозможным символам:

d[v] = 1 + \min_{w ~ : \atop (v,w,c) \in DAWG} d[[...]

Ответ на задачу будет равен d[t_0], а саму строку можно восстановить, восстановив, каким образом в динамике получился этот минимум.

Наидлиннейшая общая подстрока двух строк

Условие. Даны две строки S и T. Требуется найти их наидлиннейшую общую подстроку, т.е. такую строку X, что она является подстрокой и S, и T.

Асимптотика. Решение за O (length(S) + length(T)).

Решение. Построим суффиксный автомат по строке S.

Будем теперь идти по строке T, и для каждого префикса искать наидлиннейший суффикс этого префикса, встречающийся в S. Иными словами, мы для каждой позиции в строке T хотим найти наидлиннейшую общую подстроку S и T, заканчивающуюся именно в этой позиции.

Для этого будем поддерживать две переменные: текущее состояние v и текущую длину l. Эти две переменные будут описывать текущую совпадающую часть: её длину и состояние, которое соответствует ей (без хранения длины нельзя обойтись, поскольку одному состоянию может соответствовать сразу несколько строк разной длины).

Изначально p=t_0, l=0, т.е. совпадение пустое.

Пусть теперь мы рассматриваем символ T[i] и хотим пересчитать ответ для него.

  • Если из состояния v в автомате есть переход по символу T[i], то мы просто совершаем этот переход и увеличиваем l на единицу.

  • Если же из состояния v нет требуемого перехода, то мы должны попытаться укоротить текущую совпадающую часть, для чего надо перейти по суффиксной ссылке:

    v = link(v).

    При этом текущую длину надо укоротить, но оставить максимально возможной. Очевидно, для этого надо присвоить l = len(v), поскольку после прохода по суффиксной ссылке нас удовлетворит подстрока любой длины, соответствующая этому состоянию:

    l = len(v).

    Если из нового состояния вновь не будет перехода по требуемому символу, то мы снова должны пройти по суффиксной ссылке и уменьшить l, и так далее, пока не найдём переход (тогда перейдём к пункту 1) или мы не попадём в фиктивное состояние -1 (что означает, что символ T[i] вообще не встречается в S, поэтому присваиваем v=l=0 и переходим к следующему i).

Ответом на задачу будет максимум из значений l за всё время обхода.

Асимптотика такого прохода составляет O (length (T)), поскольку за один ход мы можем либо увеличить на единицу l, либо сделать несколько проходов по суффиксной ссылке, каждый из которых будет строго уменьшать значение l. Следовательно, уменьшений не могло быть больше length (T), что и означает линейную асимптотику.

Реализация:

string lcs (string s, string t) {
	sa_init();
	for (int i=0; i<(int)s.length(); ++i)
		sa_extend (s[i]);
 
	int v = 0,  l = 0,
		best = 0,  bestpos = 0;
	for (int i=0; i<(int)t.length(); ++i) {
		while (v && ! st[v].next.count(t[i])) {
			v = st[v].link;
			l = st[v].length;
		}
		if (st[v].next.count(t[i])) {
			v = st[v].next[t[i]];
			++l;
		}
		if (l > best)
			best = l,  bestpos = i;
	}
	return t.substr (bestpos-best+1, best);
}

Наибольшая общая подстрока нескольких строк.

Условие. Даны K строк S_i. Требуется найти их наидлиннейшую общую подстроку, т.е. такую строку X, что она является подстрокой всех S_i.

Асимптотика. Решение за O (\sum length(S_i) \cdot K).

Решение. Склеим все строки S_i в одну строку T, приписав после каждой строки S_i свой собственный символ-разделитель D_i (т.е. введя K дополнительных спец. символов D_i):

T = S_1 ~ D_1 ~ S_2 ~ D_2 ~ \ldots ~ S_k D_k.

Построим для строки T суффиксный автомат.

Теперь нам требуется найти такую строку в автомате, которая содержится во всех строках S_i, и в этом нам помогут добавленные спец. символы. Заметим, что если какая-либо подстрока входит в некоторую строку S_j, то в суффиксном автомате из этой подстроки найдётся путь, содержащий символ D_j, и не содержащий остальных символов D_1, \ldots, D_{j-1}, D_{j+1}, \ldots, D_k.

Таким образом, нам требуется посчитать достижимости: для каждого состояния автомата и каждого символа D_i есть ли путь, содержащий разделитель D_i, и не содержащий других разделителей. Это легко сделать обходом в глубину/ширину или ленивой динамикой. После этого ответом на задачу будет строка longest(v) для состояния v, из которого были найдены пути по всем символам.

Задачи в online judges

Задачи, которые можно решить с помощью суффиксного автомата:

Литература

Приведём сначала список первых работ, связанных с суффиксными автоматами:

  • A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R. McConnell. Linear Size Finite Automata for the Set of All Subwords of a Word. An Outline of Results [1983]

  • A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler. The Smallest Automaton Recognizing the Subwords of a Text [1984]

  • Maxime Crochemore. Optimal Factor Transducers [1985]

  • Maxime Crochemore. Transducers and Repetitions [1986]

  • A. Nerode. Linear automaton transformations [1958]

Помимо этого, в более современных источниках эта тема затрагивается во многих книгах по строковым алгоритмам:

  • Maxime Crochemore, Wowjcieh Rytter. Jewels of Stringology [2002]

  • Bill Smyth. Computing Patterns in Strings [2003]

  • Билл Смит. Методы и алгоритмы вычислений на строках [2006]