Как определить собственный суффикс строки в тексте

9

Суффиксы строки, которые также являются префиксом той же строки в O (n)

Недавно я столкнулся с проблемой на платформе HackerEarth, основная идея решения проблемы заключалась в том, чтобы найти, какие суффиксы строки также являются префиксом той же строки в линейном времени (по размеру строки). Например, в строке «abcdzyabc» «abc» является суффиксом строки, а также ее префиксом. Нам нужно найти все такие суффиксы за линейное время.

Теперь предположим, что у меня есть логический массив isSuffixPrefix? размера n , то есть длины строки str . isSuffixPrefix? [i] имеет значение true , если суффикс строки str начинается с индекса i , т.е. суффикс str [i . n-1] также является префиксом той же строки str , в противном случае это false . Как мы можем вычислить этот массив за линейное время (если возможно)?

Пример для строки s :

1 ответ

Ваша проблема не совсем в префиксной функции, потому что префиксная функция определяется как массив π длины n, где π [i] — длина самого длинного правильного префикса подстроки s [0… i], которая также является суффиксом эта подстрока , а не вся строка но вы можете немного настроить функцию, чтобы получить то, что вам нужно. так как функция префикса от [0..i], вы можете перевернуть слово, которое хотите, и она выдаст вам массив из [n . i], но также вам нужно будет перевернуть сам массив:

Последнее, ты сказал это

isSuffixPrefix? [2] = true // поскольку суффикс s [2..2] = «a» также является префиксом строки s

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

ACMLib

Пусть задан алфавит $\Sigma$, и на его элементах введено отношение полного порядка. Примерами такого алфавита могут служить латинские буквы с алфавитным порядком или цифры.

Будем говорить, что строка $s$ лексикографически строго меньше строки $p$, если выполнено одно из двух свойств:

1. $| s | < | p |$, и $s$ являеется префиксом $p$;
2. существует целое число $0 \le k < min(| s |, | p |)$ такое, что префиксы длины $k$ у строк $s$ и $p$ совпадают, а $s[k] < p[k]$ (здесь и далее используется 0-индексация строк).

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

Пусть теперь задана строка $s$ длины $n$. Мы можем выписать все её суффиксы и лексикографически отсортировать их. Каждый суффикс задаётся индексом своего начала, поэтому результат такой сортировки можно записать как перестановку чисел от $0$ до $n-1$. Эта перестановка называется суффиксным массивом строки $s$.

Например, суффиксным массивом строки $abracadabra$ будет перестановка $[10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]$.

Заметим, что длины всех суффиксов различны, поэтому они все попарно неравны, а значит суффиксный массив определён однозначно.

Тривиальный алгоритм

Если бы мы умели сравнивать два суффикса за время $T(n)$, то суффиксный массив можно было бы построить за время $O(n \log n \cdot T(n))$ обычной сортировкой. Сравнение строк за $O(n)$ даёт нам алгоритм за $O(n^2 \log n)$. Но если сравнивать суффиксы с помощью полиномиальный хешей и бинарного поиска, то $T(n) = O(\log n)$ и время построения суффиксного массива составит $O(n \log ^ <2>n)$.

Сортировка циклических сдвигов за $O(n \log n)$

Сперва рассмотрим немного другую задачу, хоть и очень похожую. $k$-м циклическом сдвигом строки $s$ назовём строку $s[k:]+s[:k]$, то есть строку, полученную из s переносом первого символа в конец $k$ раз. Наша задача — отсортировать циклические сдвиги строки, то есть построить суффиксный массив, в котором суффиксы рассматриваются как циклические. Циклические сдвиги могут полностью совпадать, поэтому порядок не определён однозначно; нас устроит любой правильный вариант.

Далее в описании алгоритма подразумевается циклическая индексация: $s[n] = s[0]$, $s[l:r] = s[l:] + s[:(r — n)]$, если $(l < n < r < 2 \cdot n)$ и т.д.

Алгоритм будет состоять из нескольких фаз, после $k$-й фазы будут правильно отсортированы циклические подстроки длины $2^$. Очевидно, что после $\lceil \log n \rceil$ фаз будут правильно отсортированы циклические сдвиги. Если каждую фазу выполнять за $O(n)$, то общее время работы алгоритма составит $O(n \log n)$.

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

Нулевая фаза

Нам надо отсортировать подстроки длины $2^0=1$, то есть символы. Это можно было бы сделать и за $O(n \log n)$, не ломая при этом общую асимптотику алгоритма. Однако обычно размер алфавита не превосходит размер строки, поэтому сортировку символов можно сделать подсчётом за $O(n + | \Sigma |)$.

После сортировки надо разбить символы на классы эквивалентности. Для этого мы скажем, что у $0$-го элемента суффиксного массива класс эквивалентности $0$, а потом для каждого следующего элемента суффиксного массива будем проставлять такой же класс, как и предыдущему, если они равны, и на $1$ больший иначе.

$(k+1)$-я фаза на основе $k$-й

Сейчас по плану мы должны отсортировать подстроки длины $2^$. Каждая такая подстрока имеет вид $s[p:p+2^] = s[p:p+2^] + s[(p+2^):(p+2^)+2^]$. То есть сортировка таких подстрок — то же самое, что и сортировка пар из их половинок. Но половинки мы уже отсортировали в предыдущей фазе, и даже присвоили им порядковые номера классов эквивалентности. Поэтому сортировку пар строчек можно заменить на сортировку пар чисел (номеров классов эквивалентности). Для этого можно применить поразрядную сортировку: сначала отсортировать пары по второму элементу, а потом по первому, но уже стабильно. Номера классов эквивалентности у нас до $n$, поэтому сортировать можно подсчётом за $O(n)$. На самом деле, по второму элементу пары мы уже (почти) посортировали в предыдущей фазе: суффиксный массив и является такой сортировкой, только у нас записаны индексы начал именно вторых половин подстрок, а не самих подстрок.

После сортировки нужно снова проставить классы эквивалентности, делать мы будем это так же, как и на нулевой фазе. Конечно, сравнивать на равенство нужно не подстроки длины $2^$, а пары номеров старых классов эквивалентности половинок.

Настоящий суффиксный массив

Казалось бы, суффиксы сравниваются как раз как циклические сдвиги, но это не совсем правда. Суффиксный массив строки $caba$ должен быть $[3, 1, 2, 0]$, а мы построим $[1, 3, 2, 0]$. Для строчки $aaaaa$ правильная сортировка циклических сдвигов — это любая перестановка чисел от $0$ до $4$; в то время как суффиксный массив определён однозначно. В чём же дело?

Причина в том, что если мы сравниваем два суффикса и дошли до конца строчки, то мы должны сразу более короткую из строк объявить меньшей, а вот соответствующие циклические сдвиги мы должны сравнивать дальше. Чтобы эмулировать такое поведение, припишем в конец $s$ символ, который заведомо меньше всех символов $s$. Традиционно в качестве таких символов используют \$ или #. Теперь все циклические сдвиги будут разными (потому что \$ там встречается в разных местах), причём если префиксы двух циклических строк до первого \$ совпадают, то меньше будет тот из них, в котором \$ раньше, то есть тот, который соответствует более короткому суффиксу.

В результате мы получим правильный суффиксный массив, за одним исключением: мы добавили фиктивный суффикс \$, который соответствует пустому суффиксу $s$. Очевидно, что он меньше всех остальных суффиксов, поэтому чтобы его убрать нужно просто удалить начальный элемент суффиксного массива.

Массив LCP

Массив LCP — это массив длины $n-1$, $i$-й элемент которого — это длина наибольшего общего префикса (Longest Common Prefix, LCP) суффиксов, начинающихся в позициях $SA[i]$ и $SA[i+1]$, то есть соседних в порядке сортировки.

Зачем он нужен

Было бы неплохо уметь искать длину общего префикса любых двух суффиксов, а не только соседних в каком-то непонятном порядке. Утверждается, что массив LCP может нам в этом сильно помочь.

Рассмотрим два суффикса, у одного позиция в суффиксном массиве — это $p$, у другого — $q$, $p < q$. Пусть их общий префикс имеет длину $L$. Тогда все суффиксы, позиции которых в суффиксном массиве между $p$ и $q$, также будут иметь такой же префикс длины $L$, потому что иначе они не могли бы быть между нашими двумя суффиксами в порядке сортировки. Таким образом, $\forall t \in [p, q) L \le LCP[t]$ Пусть теперь $L’ = min(LCP[p], LCP[p+1], \ldots, LCP[q-1])$. Это значит, что префикс длины $L’$ является общим для суффиксов $SA[p]$ и $SA[p+1]$, и для $SA[p+1]$ и $SA[p+2]$, и т.д. до $SA[q-1]$ и $SA[q]$. Но из этого следует, что для $SA[p]$ и $SA[q]$ префикс длины $L’$ тоже является общим. Отсюда $L \le min(LCP[p], LCP[p+1], \ldots, LCP[q-1]) = L’ \le L$, а значит $L = L’$. Таким образом, чтобы найти LCP двух произвольных суффиксов, нужно просто взять минимум на отрезке массива LCP между позициями вхождений этих суффиксов в суффиксный массив.

Алгоритм Касаи и др.

Пусть $SA[t] = p$, $SA[t+1] = q$, при этом $LCP[t] ( = LCP(s[p:], s[q:]) ) \ge 2$. Посмотрим теперь на суффиксы с началом в $(p+1)$ и $(q+1)$. Каждый из них получен отбрасыванием первого символа у суффиксов с началами $p$ и $q$, соответственно. Длина этих суффиксов была хотя бы $2$, значит наши суффиксы непустые. У суффиксов с началами в $p$ и $q$ был общий префикс длиной $LCP[t]$, значит у наших суффиксов есть общий префикс длиной хотя бы $LCP[t]-1$. Да что там хотя бы! Мы точно знали, что следующие символы различаются, при этом у суффикса с началом в $p$ следующий символ был меньше (чтобы не думать о конце строчки, будем считать, что там фиктивный \$). Поэтому у суффиксов с началом в $(p+1)$ и $(q+1)$ длина общего префикса ровно $LCP[t]-1$, и суффикс с началом в $(p+1)$ меньше, то есть идёт раньше в суффиксном массиве. Пусть его позиция там — $u$, а позиция суффикса с началом в $(q+1)$ — $v$. Тогда мы знаем, что $min(LCP[u], LCP[u+1], \ldots, LCP[v-1]) = LCP[t] — 1$. Но это значит, что $LCP[u] \ge LCP[t] — 1$.

Отсюда идея алгоритма: будем вычислять массив LCP не в порядке суффиксного массива, а в порядке самих суффиксов. Для реализации нам потребуется перестановка, обратная к суффиксному массиву.

Единственное место, время работы которого может вызывать сомнения — это внутренний цикл while. Однако заметим, что на каждой его итерации значение $curLCP$ увеличивается на $1$, а количество таких увеличений может превосходить количество уменьшений не более чем на $2n$. Количество уменьшений равно $n$; следовательно, алгоритм работает за $O(n)$ (при условии уже построенного суффиксного массива).

Замечания

Обычно мы хотим узнавать LCP для любой пары суффиксов. Как мы уже выяснили, для этого нужно брать минимум на отрезке. В данном случае чаще всего для этих целей используют sparse table, так как никаких изменений точно не будет, а на построение суффиксного массива мы все равно уже потратили $O(n \log n)$ времени. Зато на запросы мы будем отвечать за $O(1)$.

Суффиксный массив на боре

Дисклеймер: Настоятельно рекомендуется перед прочтением данного раздела прочитать и осознать построение суффиксного массива строки. Также здесь будут использоваться двоичные подъёмы.

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

Для удобства будем считать, что родитель корня — это сам корень, и на это ребре написан \$. Теперь все строчки стали бесконечными, но их лексикографический порядок не изменился. А теперь будем делать то же, что и при построении обычного суффиксного массива: алгоритм разбивается на $\lceil \log n \rceil$ фаз, после $k$-й фазы правильно отсортированы префиксы длины $2^$. Нулевая фаза не отличается вообще никак.

Как выглядит префикс длины $2^$ для строчки, соответствующей вершине $v$? Это префикс длины $2^$, а потом префикс длины $2^$ для вершины, в которую мы придём, если из $v$ $2^$ раз поднимемся в предка. Чтобы определить, что это за вершина, насчитаем двоичные подъёмы. В этом месте мы хотели заменить сортировку строк на сортировку пар номеров классов эквивалентности, а затем сортировать их с помощью поразрядной сортировки. Тут есть проблема, что одна и та же вершина может быть предком на высоте $2^$ для многих вершин, и наш финт “по второму элементу пары мы уже отсортировали на предыдущей итерации” не проходит, придётся честно сортировать сначала по второму элементу, потом по первому, и оба раза подсчётом.

Применение

Поиск подстроки (метод 1)

Дан текст $s$ и шаблон $p$, проверить, правда ли в $s$ есть подстрока, равная $p$.

Построим суффиксный массив строки $s$. Теперь суффиксы отсортированы, и можно бинарным поиском найти самый маленький суффикс, который не меньше $p$. Очевидно, если где-то и будет совпадение, так именно в этом суффиксе. На каждой итерации бинпоиска надо лексикографически сравнивать $p$ с некоторым суффиксом $s$, это можно делать за $O( | p | )$. Общее время работы — $O( | s | \log | s | + | p | \log | s | )$.

Поиск подстроки (метод 2)

Дан текст $s$ и шаблон $p$, проверить, правда ли в $s$ есть подстрока, равная $p$.

Построим строчку $ t = s + \# + p $, где # — символ, который не встречается ни в $s$, ни в $p$. Построим суффиксный массив строки $t$. Найдём в нем суффикс, соответствующий строке $p$. Кандидаты на совпадение из строки $s$ — это ближайшие (в порядке суффиксного массива) слева и справа суффиксы $s$. Найдём их линейным проходом. Осталось проверить, правда ли они подходят. Это можно сделать втупую за $O( | p | )$. Но если посчитан массив $LCP$, то достаточно взять $LCP$ соответствующих суффиксов и сравнить с длиной $p$. $LCP$ можно поддерживать вместе с поиском ближайших слева/справа суффиксов строки $s$. Общее время работы — $O( ( | s | + | p | ) \log ( | s | + | p | ) )$.

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

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

Дана строка $s$, посчитать количество её различных подстрок.

Построим суффиксный массив строки $s$ и массив $LCP$. Каждая подстрока строки — это префикс некоторого суффикса. Будем обрабатывать суффиксы в порядка суффиксного массива, и прибавлять к ответу количество тех префиксов данного суффикса ($SA[i]$), которых мы ранее не встречали. Какие префиксы мы встречали ранее? Те, у которых длина не больше, чем $LCP$ с каким-то из предыдущих суффиксов. Однако мы знаем, что $LCP$ двух суффиксов — это минимум на отрезке в массиве $LCP$. Поэтому все они ограничены сверху значением $LCP[i-1]$, а одно из значений равно $LCP[i-1]$ (собственно, $LCP$ с предыдущим суффиксом). В итоге нам нужно прибавить к ответу длину суффикса и вычесть $LCP[i-1]$. После всех итераций получаем, что ответ — это $n(n+1)/2 — \sum_^LCP[i]$ (так как сумма длин всех суффиксов это $n(n+1)/2$). Общее время работы — $O( | s | \log | s | )$.

Рефрен

Дана строка $s$. Найти её подстроку $p$ такую, что $| p | \cdot f(p, s)$ максимально, где $f(p, s)$ — количество вхождений $p$ в $s$.

(внезапно) Построим суффиксный массив строки $s$ и массив $LCP$. Пусть мы зафиксировали подстроку, которую мы хотим взять. Сколько у неё вхождений? Столько, для скольких суффиксов эта подстрока является префиксом. Все такие суффиксы в суффиксном массиве расположены рядом, то есть образуют подотрезок. Пусть теперь мы зафиксировали подотрезок в суффиксном массиве: позиции всех этих суффиксов должны быть вхождениями нашей подстроки. Разумеется, при этом мы хотим максимизировать её длину. Чему она будет равна? — $LCP$ всех этих суффиксов, то есть минимум на соответствующем отрезке в массиве $LCP$.

Теперь зафиксируем только длину ($L$) нашей будущей подстрочки. Мы уже знаем, что нам надо выбрать подотрезок суффиксного массива. Какие подотрезки нам точно нельзя выбирать? — у которых $LCP$ суффиксов строго меньше $L$, то есть в соответствующем отрезке массива $LCP$ есть значения строго меньше $L$. Фактически, такие значения в массиве $LCP$ являются перегородками: мы не можем взять суффиксы по обе стороны от этой перегородки, так как иначе $LCP$ всех суффиксов будет меньше $L$. Такие перегородки разбивают суффиксный массив на хорошие отрезки, и каждый хороший отрезок может обновить ответ своей длиной, умноженной на $L$.

Положим $L = n$, а затем будем его постепенно уменьшать. При этом перегородки будут постепенно исчезать, а хорошие отрезки — склеиваться. Этот процесс можно эмулировать, например, храня хорошие отрезки в std::set (можно обойтись и без каких-либо структур). Перегородок у нас $(n-1)$, поэтому удалений перегородок будет не больше. При уменьшении $L$ ответ для всех старых отрезков только уменьшиться, поэтому пробегаться по всем отрезкам не нужно. Реальные кандидаты на ответ могут появиться только при удалении перегородки, это будет как раз только что созданный хороший отрезок.

Все это может быть реализовано за $O(| s | \log | s | )$.

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

Алгоритмы C++

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

for ( int i= 0 ; i<n- 1 ; ++i )

lcp [ i ] = min ( lcp [ i ] , min ( n-p [ i ] , n-p [ i+1 ])) ;

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

for ( int i= 0 ; i<n; ++i ) pos [ p [ i ]] = i; rmq_build ( lcp, n-1 ) ;

. поступил запрос ( i,j ) на нахождение LCP .

int result = rmq ( min ( i,j ) , max ( i,j ) -1 ) ;

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

Выполним препроцессинг , описанный в предыдущем разделе: за времени и памяти мы

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

Для этого будем рассматривать, какие новые подстроки начинаются в позиции , затем в позиции , и т.

д. Фактически, мы берём очередной в порядке сортировки суффикс и смотрим, какие его префиксы дают новые подстроки. Тем самым мы, очевидно, не упустим из виду никакие из подстрок.

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

даст в качестве

новых подстрок все свои префиксы, кроме совпадающих с префиксами суффикса

. Т.е. все его префиксы,

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

то окончательно получаем, что текущий суффикс

новых подстрок. Суммируя это

по всем суффиксам (для самого первого,

, отнимать нечего — прибавится просто

Формальное определение. Суффиксным автоматом (suffix automaton) строки S называется

минимальный детерминированный автомат, который распознаёт все суффиксы строки S, и только их. (суффиксами также считаются вся строка, а также пустая строка). В англоязычной литературе суффиксный автомат называется suffix automaton (во множественном числе automata), а также DAWG (directed acyclic word graph).

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

«распознаёт строку», если, стартуя из начального состояния Init, выполнив последовательно переходы по символам этой строки, мы придём в терминальное состояние (если в какой-то момент мы попытались пройти по несуществующему переходу, то мы останавливаемся, и автомат такую строку не распознаёт).

Соответственно, суффиксным автоматом будет называться только тот автомат, который распознаёт все суффиксы строки, а любые другие строки распознавать не будет.

Условимся говорить, что некоторой строке T соответствует состояние p, если, стартовав в состоянии Init и выполнив все переходы по символам этой строки T, мы придём в состояние p. Например, можно говорить, что

любому суффиксу строки S (по которой построен автомат) соответствует терминальное состояние, а любой другой строке — соответствует нетерминальное состояние, или вовсе никакое состояние не соответствует (если в какой-то момент мы попытались совершить несуществующий переход).

Итак, пусть дана строка S длины N в некотором алфавите размера K. Требуется построить суффиксный автомат для неё.

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

Состояния будем обозначать числами (за исключением начального состояния Init), терминальные состояния — отмечать звёздочками, переходы — стрелочками с подписанными поверх них буквами.

Анализ суффиксного автомата

Проведём сначала анализ суффиксного автомата.

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

Во-вторых, число состояний в нём не более 2N-1 (за исключением N=1 и N=2, для них будет 1 и 3

состояния соответственно); этот факт мы пока примем без доказательства, он будет вытекать из корректности описанного ниже алгоритма построения суффиксного автомата.

В-третьих, число переходов — не более 3N-4 (за исключением, опять же, N=1 и N=2); доказательство этого факта мы также приведём после описания самого алгоритма.

Таким образом, мы обнаружили удивительный факт: суффиксный автомат имеет размер O (N) , несмотря

на то, что суммарная длина всех суффиксов строки есть величина O (N 2 ). Более того, ниже будет будет описан алгоритм, строящий суффиксный автомат также за линейное время (правда, с потреблением памяти O (N K); если же необходимо экономно использовать память — O (N), то время работы алгоритма увеличивается до O (N log K); более подробно см. в следующем разделе).

Рассмотрим теперь наихудшие тесты для суффиксного автомата. Несложно заметить, что для строки вида «abbb. » будет достигаться наибольшее число состояний. Также непосредственной проверкой можно убедиться в том, что строка вида «abbb. bbbc» является наихудшей с точки зрения количества переходов.

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

Для описания алгоритма нам потребуется ввести ещё две дополнительных характеристики для каждого состояния: length

Для некоторого состояния p величина length равна длине наидлиннейшего пути из Init в p. Иными словами, length — это длина наидлиннейшего слова, под воздействием которого автомат из состояния Init переходит в состояние p.

Суффиксная ссылка link для состояния p определяется следующим образом. Рассмотрим наидлиннейший путь из состояния Init в p, ему соответствует некоторая строка. Суффиксная ссылка не определена только для

начального состояния Init. Найдём такой наибольший суффикс этой строки, что ему (этому суффиксу) соответствует некоторое состояние q, отличное от p. Из самого определения следует, что суффикс может быть только собственным, а length[p] > length[q].

Сразу же определим понятие суффиксного пути для некоторого состояния p. Суффиксный путь —

это последовательность (p, link[p], link[link[p]], . ), конечная (поскольку длины length вдоль пути строго убывают, и при этом они всегда неотрицательны). Легко понять, что суффиксный путь всегда завершается состоянием Init. Если для некоторого состояния p мы будем двигаться по его суффиксному пути, то мы будем фактически двигаться

по суффиксам строки, соответствующей состоянию p.

Теперь опишем сам алгоритм . Он будет итеративным (в режиме on-line), т.е. сначала создаст автомат для пустой строки, а потом будет последовательно добавлять символы строки S, перестраивая автомат.

Единственное исключение — что метки «терминальный» будут расставляться за O (N) уже после построения автомата для всей строки.

Введём сразу тип данных «состояние автомата», где таблицу переходов представим для каждого состояния в виде массива величиной K. Состояния будем хранить для удобства в виде статического массива размером MAXLEN*2-1 (где MAXLEN — заранее известная константа — ограничение на длину строки), хотя, понятно, легко будет исправить весь код на использование динамического vector.

const int MAXLEN = . ; // максимальная длина строки const int K = . ; // размер алфавита

int length, link; int next[K]; bool termimal;

state st[MAXLEN*2-1]; int sz = 0;

int last; // указывает на «последнее» состояние, т.е. то, в которое ведёт самый длинный путь из Init

Итак, сначала создадим суффиксный автомат для пустой строки, он состоит только из начального состояния Init (у него будет номер 0 в массиве st):

st[0].length = 0; st[0].link = -1;

memset (st[0].next, -1, sizeof st[0].next); // делаем все next == -1 ++sz;

Итак, пусть теперь автомат уже построен для некоторой строки W, и мы хотим перестроить его для строки S = W+C, где C — некоторый символ. Реализуем эту операцию в виде функции sa_extend (char c).

Создадим сразу новое состояние nlast, которому по окончании работы sa_extend будет соответствовать строка S. Пока что у этого состояния мы знаем только длину length и то, что переходов из него не будет:

void sa_extend (char c) < int nlast = sz++;

st[nlast].length = st[last].length + 1;

memset (st[nlast].next, -1, sizeof st[nlast].next);

После этого мы хотим рассмотреть строку W и все её суффиксы, и дописать к ним символ C, т.е. добавить переходы по символу C в состояние nlast. Вспоминая понятие суффиксного пути, мы можем это сформулировать кратко: пройдёмся по суффиксному пути состояния last и добавим из каждого посещённого состояния переход по символу С в состояние nlast. Однако, если в какой-то момент мы столкнёмся с тем, что такой переход уже существует —

мы вынуждены будем остановиться; этот случай мы рассмотрим ниже.

for (; p!=-1 && st[p].next[c]==-1; p=st[p].link) st[p].next[c] = nlast;

Теперь у нас есть два случая: 1) если мы ни разу не столкнулись с уже существующим переходом, тогда p==-1, и 2) если остановились на таком переходе.

Случай 1) — самый простой. Он означает, что символ C ещё ни разу не встретился в строке W. Мы добавили переходы из каждого суффикса строки W по символу C в строку S, больше нам никаких переходов добавлять не нужно. Осталось только установить суффиксную ссылку для состояния nlast, но она будет указывать, очевидно, на Init (это как раз следует из того, что символ C встретился нам впервые). Итак, мы можем реализовать этот случай:

if (p == -1) st[nlast].link = 0;

Случай 2) распадается также на два случая 2а и 2б. Итак, мы остановились на состоянии p, из которого уже есть переход по символу С, обозначим через q состояние, в которое ведёт этот переход. Если length[p] + 1 == length[q], то это случай 2а, иначе случай 2б (сейчас мы поймём смысл этого равенства).

Случай 2а), т.е. length[p] + 1 == length[q] (в этом случае говорят, что переход из состояния p в состояние

q «сплошной» (solid)). Обозначим через U длиннейшую строку, соответствующую состоянию p (т.е. U.length() == length [p]). Строка U+C является наидлиннейшим суффиксом строки S = W+C, встречающимся в W (иное и

невозможно, поскольку тогда бы мы раньше обнаружили существующий переход по символу C), а потому мы должны провести суффиксную ссылку в то состояние, которому соответствует строка U+A и при этом

является наидлиннейшей для него. Вспоминая, что length[q] == length[p] + 1 == (U+C).length(), мы как раз и получаем, что строка U+C является наидлиннейшей для состояния q, и мы можем провести суффиксную ссылку из состояния nlast в состояние q. Наконец, можно утверждать, что больше никаких переходов добавлять не надо — строка U+C вместе

со всеми своими суффиксами уже была обработана ранее (ведь она уже присутствовала в W).

int q = st[p].next[c];

if (st[p].length + 1 == st[q].length)

Случай 2б), т.е. length[p] + 1 != length[q] (из вышеописаных свойств можно утверждать, что length[p] + 1 < length[q]).

Снова, как и в случае 2а), обозначим через U длиннейшую строку для состояния p. Снова мы утверждаем, что строка U +C является наидлиннейшим суффиксом строки S, встречающимся в W, а потому суффиксную ссылку из состояния nlast нам хотелось бы провести в состояние, где эта строка U+C является длиннейшей. Однако на этот раз

такого состояния не существует: length[q] > length[p] + 1 == (U+C).length(), и при этом самой строке U+C соответствует состояние q. Тут нам приходится выполнить более хитрое преобразование автомата — мы вынуждены расщепить состояние q на два состояния, для одного из которых строка U+C будет длиннейшей. Создадим новое состояние clone, и перенаправим в него часть переходов в q. Нам нужно перенаправить переходы, соответствующие строке U+C и всем её суффиксам (точнее говоря, всем суффиксам строки U и плюс символ C). Вспоминая, что строке U как раз соответствует состояние p, и вспоминая понятие суффиксного пути,

мы получаем такую формулировку: продолжим двигаться по суффиксному пути состояния p, и, пока есть переход из него в состояние q по символу C, будем перенаправлять этот переход на состояние clone. Теперь разберёмся с

новым состоянием clone, нам же нужно заполнить его параметры. Его длина length равна длине строки U+C, т.е. length[p] + 1. Его суффиксная ссылка ведёт туда, куда вела суффиксная ссылка состояния q. Наконец, переходы из clone

надо скопировать из состояния q (отсюда и название состояния — «clone»). Осталось только заметить, что суффиксная ссылка для состояния q теперь изменится — она будет указывать, разумеется, на состояния clone (ведь мы отделили строки U+C и короче неё, вот на них теперь и будет указывать суффиксная ссылка). Ну и, разумеется, суффиксная ссылка для состояния nlast будет также указывать на clone (для чего собственно и выполнялось это расщепление).

st[clone].length = st[p].length + 1;

memcpy (st[clone].next, st[q].next, sizeof st

for (; p!=-1 && st[p].next[c]==q; p=st[p].link) st[p].next[c] = clone;

st[q].link = st[nlast].link = clone;

Наконец, завершаем функцию sa_extend, не забывая обновить значение last:

Теперь осталось только научиться проставлять значения terminal (правда, при решении большинства задач эти значения просто не нужны). Это очень легко сделать: рассмотрим состояние last и его суффиксный путь.

Этим состояниям как раз и соответствуют строка S и все её суффиксы, причём только они (это следует непосредственно из определения суффиксной ссылки):

for (int p=last; p!=-1; p=st[p].link) st[p].terminal = true;

Приведём сначала обещанные доказательства того, что состояний в суффиксном автомате не более 2N-1, а переходов — 3N-4 (для N>=3).

Оценка на число состояний непосредственно вытекает из корректности алгоритма — мы добавляем одно состояние Init при создании, и добавляем на каждом шаге по одному или двум состояниям; при этом сразу два состояния могут быть добавлены только начиная с третьего шага; итого и получается 1 + N + N-2 = 2N-1.

Оценим теперь максимальное число переходов. Рассмотрим остовное дерево из длиннейших путей в

автомате, начинающихся в вершине Init. Оно будет содержать только сплошные рёбра (причём всех их), и их будет на единицу меньше, чем число состояний. Теперь оценим число несплошных рёбер. Поставим каждому

несплошному ребру из p в q по символу C такую строку: U+C+V, где U — строка, соответствующая длиннейшему пути из Init в p, V — строка, соответствующая длиннейшему пути из q в некоторое терминальное состояние. Заметим, что разным несплошным рёбрам будут соответствовать разные строки U+C+V. С другой стороны, в силу самого построения этой строки, эта строка U+C+V будет суффиксом строки S. Поскольку число различных суффиксов есть N+1, а суффиксы S и «» не могли быть учтены (потому что они входят в остовное дерево), то в итоге несплошных рёбер

не более N-1. Складывая количества сплошных и несплошных рёбер, получаем оценку 3N-4.

Оценим теперь асимптотику алгоритма. Нам нужно оценить суммарное время работы двух циклов for внутри функции sa_extend. С первым циклом всё понятно — на каждой своей итерации он добавляет новый переход, а т.к. число переходов есть O (N), а переходы никогда не удаляются, то суммарное время работы первого цикла есть O

(N). Второй цикл так оценить не получится, поскольку он новых переходов не добавляет. Обозначим через

V наидлиннейшую строку, соответствующую состоянию p. Перед выполнением итерации этого цикла V является K- ым (K>=2) элементом в суффиксном пути W, а после него V+C является 2-ым элементом в суффиксном пути W+C, и потому позиция V как суффикса W строго увеличивается на каждой итерации этого цикла, причём не только в пределах одного вызова функции sa_extend, а в пределах всех вызовов. Потому число выполнений этого цикла также равно O (N).

Итак, если переходы next хранить в виде массива, то получаем асимптотику алгоритма O (N K) (хотя и с очень малой константой, т.к. все действия, за исключением копирования массивов memcpy, выполняются за O (N)), но при использовании памяти O (N K) .

Впрочем, на массивах можно достичь и настоящей линейной асимптотики, если вдобавок к массивам хранить списки переходов (в виде vector< pair<char,int> >). Тогда копирование переходов будет осуществляться за O() от количества переходов из текущего состояния, а не за O (K).

Однако, если хранить переходы сжато, например, в виде map<char,int>, то время работы алгоритма увеличится до O (N log K) , но зато уменьшится используемая память до O (N) .

Поскольку весь приведённый выше код равномерно «размазан» по тексту, приведём здесь полную реализацию (работающую за O (N K) (как уже говорилось, на пратике — близко к O (N), поскольку O (N K) операций связаны с копированием массивов вызовами memcpy, которые выполняются очень быстро) при потреблении памяти O (N K) :

const int MAXLEN = . ; // максимальная длина строки const int K = . ; // размер алфавита

int length, link; int next[K]; bool termimal;

state st[MAXLEN*2-1]; int sz, last;

// эти действия нужны, если автомат строится несколько раз для разных строк:

Суффструктуры- Суффиксный массив, суффиксное дерево NP-трудные задачи

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

суффструктуры

Суффструктуры — это структуры представления суффиксов строк, примерами таких структур являются суффиксерк дерево и суффиксны массив, Используются в алгоритмах поиска подстроки в строке, определении схожести строк и других.

Рассмотрим эти структуры подробнее.

суффиксное дерево

Суффиксное дерево — бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.

Основные определения и описание структуры

— непустое конечное множество символов, называемое алфавитом. Последовательность символов (возможно, пустая) из алфавита обозначается буквами r, s и t. представляет собой перевернутую строку. Отдельные символы обозначаются буквами x, y или z. — пустая строка. Символами из алфавита являются буквы a, b, …. Пока размер алфавита принимается постоянным. |t| обозначает длину строки t. — все строки длины m, и .

Префикс w строки t — строка такая, что wv = t для некоторой (возможно, пустой) строки v. Префикс называется собственным, если |v| 0.

Суффикс w строки t — строка такая, что vw = t для некоторой (возможно, пустой) строки v. Суффикс называется собственным, если |v| 0. Например, для строки «substring» подстрока «sub» является собственным префиксом, «ring» — собственным суффиксом.

Подстрока w строки t называется правым ветвлением, если t может быть представлена как и для некоторых строк и , а также букв x y. Левое ветвление определяется аналогично. Например, для «eabceeabcd» подстрока «abc» является правым ветвлением, так как в обоих ее вхождениях в t справа от нее стоят различные символы, зато та же подстрока не является левым ветвлением, потому что слева от нее в обоих вхождениях стоит одинаковый символ «e».

—дерево T — корневое дерево с ребрами, помеченными последовательностями из . Для каждого символа a из алфавита каждый узел в дереве T имеет не более одного ребра, метка которого начинается c символа a. Ребро от t до s с меткой v мы будем обозначать .

Пусть k — узел -дерева T, тогда path(k) — строка, которая представляет собой конкатенацию всех меток ребер от корня до k. Мы назовем местоположением w, для которого path() = w.

Так как каждая ветвь уникальна, если path(t) = w, мы можем обозначить узел t за . Поддерево узла обозначается.

Слова, которые представлены в -дереве T, задаются множеством, которое обозначается words(T). Слово w входит во множество words(T) тогда и только тогда, когда существует строка v (возможно, пустая) такая, что — узел дерева T.

Если строка w входит в words(T), w = uv, — узел дерева T, пару будем называть ссылочной парой w по отношению к дереву T. Если u — наидлиннейший префикс такой, что — ссылочная пара, мы будем называть канонической ссылочной парой. Тогда мы будем писать . Местоположение называется явным, если |v| = 0, и неявным в противном случае.

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

Атомарное -дерево также называют (луч). Атомарное и компактное -дерево однозначно определены словами, которые они содержат.

Суффиксное дерево для строки t — это -дерево такое, что words(T) = <w| w — подслово t>. Для строки t атомарное суффиксное дерево обозначается ast(t), компактное суффиксное дерево обозначается cst(t).

Обратное префиксное дерево строки t — это суффиксное дерево для строки .

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

Свойства суффиксных деревьев

Лемма. Местоположение w явно в компактном суффиксном дереве тогда и только тогда, когда w является не вложенным суффиксом t или w — правое ветвление.

Доказательство. . Если явно, то это может быть либо лист, либо вершина ветвления или корень (в этом случае и w — вложенный суффикс t).

Если — лист, тогда также является и суффиксом t. Значит, это должен быть не вложенный суффикс, так как иначе он появился бы где-нибудь еще в строке t: v — суффикс t такой, что w — префикс v. Этот узел не может быть листом.

Если — узел ветвления, тогда должны существовать, по меньшей мере, два выходящих ребра из с различными метками. Это означает, что существуют два различных суффикса u, v, что w — префикс u и w — префикс v, где v = wxs, u = , x . Следовательно, w — правое ветвление.

. Если w является не вложенным суффиксом t, это должен быть лист. Если w — правое ветвление, то имеются два суффикса u и v, u = wxs, v = , x , тогда w является узлом ветвления. Лемма доказана.

Теперь легко видеть, почему ответ на вопрос, входит ли слово w в строку t, может быть найден за время O(|w|): нужно только проверить, является ли w местоположением (явным или неявным) в cst(t).

Метки ребер должны представлять собой указатели на положение в строке, чтобы суффиксное дерево расходовало память размером O(n). Метка (p, q) ребра означает подстроку или пустую строку, если p > q.

Укконен вводит название открытые ребра для ребер, заканчивающихся в листьях. Пометки открытых ребер записывают как (p, ) вместо (p, |t|), где — длина, всегда большая, чем |t|.

Пусть T — -дерево. Пусть — узел T, v — наидлиннейший суффикс w такой, что — также узел T. Непомеченное ребро от до называется суффиксным звеном. Если v = w, оно называется атомарным.

Утверждение. В ast(t) и cst(t$), где $ t, все суффиксные звенья являются атомарными.

Доказательство. Символ $ называется символом-стражем. Первая часть (для ast(t)) следует из определения, так как местоположения являются явными. Для доказательства второй (случай cst(t)) части мы должны показать, что для каждого узла также является узлом cst(t). Если — узел cst(t), то является либо листом, либо узлом ветвления. Если является листом, тогда aw — не вложенный суффикс t. Благодаря символу-стражу, из леммы следует, что все суффиксы (включая корень, пустой суффикс) являются явными, так как только корень — вложенный суффикс. Поэтому w является листом или корнем. Если — узел ветвления, тогда aw — правое ветвление, как и w. Следовательно, местоположение явно по лемме. Утверждение доказано.

Как следует из этого доказательства, символ-страж гарантирует существование листьев для всех суффиксов. С таким символом не может быть вложенных суффиксов, кроме пустого. Если мы опустим символ-страж, некоторые суффиксы могут стать вложенными, и их местоположения станут неявными.

Требования суффиксного дерева к памяти

Утверждение. Компактное суффиксное дерево может быть представлено в виде, требующем O(n) памяти.

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

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

Аналогично, каждый узел имеет не более одного суффиксного звена, тогда общее число суффиксных звеньев также ограничено числом 2n. Утверждение доказано.

Как пример суффиксного дерева с 2n-1 вершинами можно рассмотреть дерево для слова . Размер атомарного суффиксного дерева для строки t составляет O().

Построение дерева за линейное время. Алгоритм mcc. (McCreight’s Algorithm)

Алгоритм mcc начинает работу с пустого дерева и добавляет суффиксы начиная с самого длинного. Алгоритм mcc не является on-line алгоритмом, то есть для его работы необходима вся строка целиком . Об этом говорит сайт https://intellect.icu . Для корректной работы требуется, чтобы строка завершалась специальным символом, отличным от других, так, чтобы ни один суффикс не являлся префиксом другого суффикса. Каждому суффиксу в дереве будет соответствовать лист. Для алгоритма мы определим — текущий суффикс (на шаге ), (голова) — наибольший префикс суффикса , который является также префиксом другого суффикса , где . (хвост) определим как.

Ключевой идеей алгоритма mcc является соотношение между и .

Лемма. Если где — буква алфавита, — строка (может быть пустая), тогда — префикс .

Доказательство. Пусть . Тогда существует, , такой, что является как префиксом , так и префиксом . Тогда — префикс и , следовательно, является префиксом головы . Лемма доказана.

Мы знаем местоположение , и если мы будем иметь суффиксное звено, то можем быстро перейти к местоположению — префикса головы без необходимости находить путь от корня дерева. Но местоположение > могло бы не являться явным (если местоположение не было явным на предыдущем шаге) и суффиксное звено могло бы быть еще не установлено для узла. Решение, данное МакКреем, находит узел за два шага: «повторное сканирование» («rescanning») и «сканирование» («scanning»). Мы проходим дерево наверх от узла пока не найдем суффиксное звено, следуем по нему и затем применяем повторное сканирование пути до местоположения (которое является простым, потому что мы знаем длину и это местоположение существует, так что мы не должны читать полные метки ребер, двигаясь вниз по дереву, мы можем просто проверять только начальные буквы и длину слов).

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

Алгоритм состоит из трех частей.

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

2. Затем он повторно сканирует часть предыдущей головы, для которой длина является известной (эта часть названа ).

3. Наконец алгоритм устанавливает суффиксное звено для , сканирует оставшуюся часть (названную) и добавляет новый лист для .

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

Обратите внимание, что если тогда и узнается одинаково быстро, как следуя суффиксному звену согласно строке 7 алгоритма.

Процедура Rescan ищет местоположение . Если местоположение еще не явно, добавляется новый узел. Этот случай имеет место, когда голова ( ) просмотрена целиком: если голова длиннее (и узел уже определен), > должно являться префиксом более чем двух суффиксов и также является левым ветвлением . Местоположение может являться только явным, если этот узел уже является узлом ветвления, и если не было левым ветвлением тогда , должно быть, был длиннее, потому что встретился более длинный префикс.

Процедура Scan производит поиск в глубину дерева и возвращает позицию.

Построение дерева за линейное время. Алгоритм ukk.

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

Для алгоритма Укконена нам потребуются

Неявные суффиксные деревья.

Суффиксное дерево для строки xabxa$

Неявное суффиксное дерево для строки xabxa$

Алгоритм Укконена строит последовательность неявных суффиксных деревьев, последнее из которых преобразуется в настоящее суффиксное дерево строки S.

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

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

Хотя неявное суффиксное дерево может иметь листья не для всех суффиксов, в нем закодированы все суффиксы S — каждый произносится символами какого-либо пути от корня этого неявного суффиксного дерева. Однако если этот путь не кончается листом, то не будет маркера, обозначающего конец пути. Таким образом, неявные суффиксные деревья сами по себе несколько менее информативны, чем настоящие. Мы будем использовать их только как вспомогательное средство в алгоритме Укконена, чтобы получить настоящее суффиксное дерево для S.

Общее описание алгоритма.

Алгоритм Укконена строит неявное суффиксное дерево Ti для каждого префикса S[l..i] строки S, начиная с T1 и увеличивая i на единицу, пока не будет построено Tm. Настоящее суффиксное дерево для S получается из Tm, и вся работа требует времени О(m). Мы объясним алгоритм Укконена, представив сначала метод, с помощью которого все деревья строятся за время O(m³), а затем оптимизируем реализацию этого метода так, что будет достигнута заявленная скорость.

Три правила продолжения суффикса.

Чтобы превратить это общее описание в алгоритм, мы должны точно указать, как выполнять продолжение суффикса. Пусть S[j..i] = β — суффикс S[1..i]. В продолжении j, когда алгоритм находит конец β в текущем дереве, он продолжает β, чтобы обеспечить присутствие суффикса βS(i + 1) в дереве. Алгоритм действует по одному из следующих трех правил.

Правило 1. В текущем дереве путь β кончается в листе. Это значит, что путь от корня с меткой β доходит до конца некоторой «листовой» дуги (дуги, входящей в лист). При изменении дерева нужно добавить к концу метки этой листовой дуги символ S(i + 1).

Правило 2. Ни один путь из конца строки β не начинается символом S(i + 1), но по крайней мере один начинающийся оттуда путь имеется. В этом случае должна быть создана новая листовая дуга, начинающаяся в конце β, помеченная символом S(i + 1). При этом, если β кончается внутри дуги, должна быть создана новая вершина. Листу в конце новой листовой дуги сопоставляется номер j. Таким образом, в правиле 2 возможно два случая.

Правило 3. Некоторый путь из конца строки β начинается символом S(i + 1). В этом случае строка βS(i + 1) уже имеется в текущем дереве, так что ничего не надо делать (в неявном суффиксном дереве конец суффикса не нужно помечать явно).

суффиксный массив

Суффиксный массив — лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти. Она часто применяется там, где необходим быстрый поиск подстрок, например в преобразовании Барроуза — Уилера (BWT), а также в качестве структуры данных в поисковом индексе.

Дана строка длины .

-ым суффиксом строки называется подстрока , .

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

Например, для строки суффиксный массив будет равен:

История

В 1989 году Манбер и Майерс опубликовали статью, в которой описали такую структуру данных, как суффиксный массив, и как ее применять для поиска подстрок. Суффиксный массив — это массив лексикографически отсортированных суффиксов строк (если терминология незнакома, то можно глянуть раздел «постановка задачи» в этой статье). Вообще говоря, хранить сами суффиксы смысла нет, достаточно хранить позицию начала данного суффикса, но определение массива так легче воспринимается. Вот пример для строки «mississippi»:

Пример

Рассмотрим строку «abracadabra» длиной 11 символов.

Отсортированный список ее суффиксов:

Суффиксный массив этой строки — <11,8,1,4,6,9,2,5,7,10,3>, потому что суффикс «a» начинается с 11-го знака, суффикс «abra» — с 8-го, и так далее, вплоть до последнего суффикса «racadabra», который начинается с третьего символа исходного слова.

Теперь с помощью этого массива можно легко найти все подстроки. Например, если нужно найти подстроку «ab», достаточно найти все суффиксы, которые начинаются на «ab». За счет сортировки по алфавиту, они находятся рядом друг с другом. Используя бинарный поиск, мы находим 2-й и 3-й суффиксы «abra» и «abracadabra», которым соответствуют 2-й и 3-й элемент суффиксного массива (8 и 1). Это означает, что искомая подстрока «ab» встречается на первом и восьмом символе в исходном слове.

Применения суффструктур

Нахождение наименьшего циклического сдвига строки

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

Поиск подстроки в строке

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

Сравнение двух подстрок строки

Требуется по заданной строке , произведя некоторый ее препроцессинг, научиться за отвечать на запросы сравнения двух произвольных подстрок (т.е. проверка, что первая подстрока равна/меньше/больше второй).

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

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

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

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

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

Требуется по заданной строке , произведя некоторый ее препроцессинг, научиться за отвечать на запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями и .

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

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

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

Здесь через обозначена константа, равная логарифму по основанию 2, округленному вниз.

Наибольший общий префикс двух подстрок: способ без дополнительной памяти. Наибольший общий префикс двух соседних суффиксов

Требуется по заданной строке , произведя некоторый ее препроцессинг, научиться отвечать на запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями и .

В отличие от предыдущего метода, описываемый здесь будет выполнять препроцессинг строки за времени с памяти. Результатом этого препроцессинга будет являться массив (который сам по себе является важным источником информации о строке, и потому использоваться для решения других задач). Ответы же на запрос будут производиться как результат выполнения запроса RMQ (минимум на отрезке, range minimum query) в этом массиве, поэтому при разных реализациях можно получить как логарифмическое, так и константное времена работы.

Базой для этого алгоритма является следующая идея: найдем каким-нибудь образом наибольшие общие префиксы для каждой соседней в порядке сортировки пары суффиксов. Иными словами, построим массив , где равен наибольшему общему префиксу суффиксов и . Этот массив даст нам ответ для любых двух соседних суффиксов строки. Тогда ответ для любых двух суффиксов, не обязательно соседних, можно получить по этому массиву. В самом деле, пусть поступил запрос с некоторыми номерами суффиксов и . Найдем эти индексы в суффиксном массиве, т.е. пусть и — их позиции в массиве (упорядочим их, т.е. пусть ). Тогда ответом на данный запрос будет минимум в массиве , взятый на отрезке . В самом деле, переход от суффикса к суффиксу можно заменить целой цепочкой переходов, начинающейся с суффикса и заканчивающейся в суффиксе , но включающей в себя все промежуточные суффиксы, находящиеся в порядке сортировки между ними.

Таким образом, если мы имеем такой массив alt=»Суффструктуры- Суффиксный массив, суффиксное дерево NP-трудные задачи» />, то ответ на любой запрос наибольшего общего префикса сводится к запросу минимума на отрезке массива alt=»Суффструктуры- Суффиксный массив, суффиксное дерево NP-трудные задачи» />. Эта классическая задача минимума на отрезке (range minimum query, RMQ) имеет множество решений с различными асимптотиками, описанные здесь.

Итак, основная наша задача — построение этого массива alt=»Суффструктуры- Суффиксный массив, суффиксное дерево NP-трудные задачи» />. Строить его мы будем по ходу алгоритма построения суффиксного массива: на каждой текущей итерации будем строить массив alt=»Суффструктуры- Суффиксный массив, суффиксное дерево NP-трудные задачи» />для циклических подстрок текущей длины.

После нулевой итерации массив , очевидно, должен быть нулевым.

Пусть теперь мы выполнили -ю итерацию, получили от нее массив , и должны на текущей -й итерации пересчитать этот массив, получив новое его значение . Как мы помним, в алгоритме построения суффиксного массива циклические подстроки длины разбивались пополам на две подстроки длины ; воспользуемся этим же приемом и для построения массива .

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

1) Первые половинки подстрок различались. Заметим, что тогда на предыдущем шаге эти первые половинки необходимо были соседними. В самом деле, классы эквивалентности не могли исчезать (а могут только появляться), поэтому все различные подстроки длины дадут (в качестве первых половинок) на текущей итерации различные подстроки длины , и в том же порядке. Таким образом, для определения в этом случае надо просто взять соответствующее значение из массива .

2) Первые половинки совпадали. Тогда вторые половинки могли как совпадать, так и различаться; при этом, если они различаются, то они совсем не обязательно должны были быть соседними на предыдущей итерации. Поэтому в этом случае нет простого способа определить . Для его определения надо поступить так же, как мы и собираемся потом вычислять наибольший общий префикс для любых двух суффиксов: надо выполнить запрос минимума (RMQ) на соответствующем отрезке массива .

Оценим асимптотику такого алгоритма. Как мы видели при разборе этих двух случаев, только второй случай дает увеличение числа классов эквивалентности. Иными словами, можно говорить о том, что каждый новый класс эквивалентности появляется вместе с одним запросом RMQ. Поскольку всего классов эквивалентности может быть до , то и искать минимум мы должны за асимптотику . А для этого надо использовать уже какую-то структуру данных для минимума на отрезке; эту структуру данных надо будет строить заново на каждой итерации (которых всего ). Хорошим вариантом структуры данных будет Дерево отрезков: его можно построить за , а потом выполнять запросы за , что как раз и дает нам итоговую асимптотику .

Реализация:

Здесь помимо массива вводится временный массив с его новым значением. Также поддерживается массив , который для каждой подстроки хранит ее позицию в перестановке . Функция — некоторая функция, строящая структуру данных для минимума по массиву-первому аргументу, размер его передается вторым аргументом. Функция возвращает минимум на отрезке: с первого аргумента по второй включительно.

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

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

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

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

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

Для этого будем рассматривать, какие новые подстроки начинаются в позиции , затем в позиции , и т.д. Фактически, мы берем очередной в порядке сортировки суффикс и смотрим, какие его префиксы дают новые подстроки. Тем самым мы, очевидно, не упустим из виду никакие из подстрок.

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

См. также

• Суффиксный автомат
• Алгоритм Касаи построения массива наибольших общих префиксов.
• Обобщенное суффиксное дерево

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