Декомпозиция Линдона

Декомпозиция Линдона была изобретена Роджером Линдоном (англ. Roger Lyndon) в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.

Основные определения

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

Простая строка — строка, которая лексикографически меньше любого своего суффикса.

Примеры:

[math]ababb[/math] — простая строка, так как [math]ababb \lt babb[/math], [math]ababb \lt abb[/math], [math]ababb \lt bb[/math], [math]ababb \lt b[/math].

[math]babaa[/math] — не простая строка, так как [math]babaa \gt aa[/math].

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

Декомпозиция Линдона (англ. Lyndon decomposition) строки [math]s[/math] — её разложение [math]s = s_1s_2...s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math].

Существование и единственность

Лемма:

[math]s [/math], [math]t[/math] — простые и [math]s \lt t[/math] лексикографически. Тогда верны следующие утверждения: 1. [math]s + t \lt t[/math] 2. [math]s + t[/math] — простая

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

[math]\triangleright[/math]

1. Так как [math]s \lt t[/math], то [math]\exists i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i \Rightarrow s + t \lt t[/math] 2. Пусть [math]u[/math] — суффикс строки [math]s + t[/math]. Тогда рассмотрим 3 возможных случая: [math]|u| = |t| \Rightarrow u = t \Rightarrow u \gt s + t[/math] по пункту 1 [math]|u| \lt |t| \Rightarrow u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] — простая, и [math]t \lt u [/math] по определению [math] \Rightarrow s + t \lt t \lt u[/math] [math]|u| \gt |t| \Rightarrow s = s' + s''[/math], [math]u = s'' + t[/math]. Так как [math]s[/math] — простая, то её суффикс [math] s'' [/math] меньше самой строки [math] s [/math] в каком-то символе, значит, [math] s + t \lt s'' + t[/math]

[math]\triangleleft[/math]

Теорема (Чен-Линдон-Фокс):

Можно построить декомпозицию Линдона любой строки [math]s[/math], причем единственным образом.

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

[math]\triangleright[/math]

1. Существование. У каждой строки существует хотя бы одно разбиение на простые слова. Это следует из того, что отдельный символ является простым словом. Тогда среди всех разбиений строки на простые слова возьмём то, в котором меньше всего слов. Покажем, что это и будет декомпозицией Линдона данной строки. Предположим, что это не так. Значит, [math]\exists i : s_i \lt s_{i+1}[/math]. Так как слова [math] s_i [/math] и [math] s_{i+1} [/math] простые, то из доказанной леммы следует, что эти слова можно сконкатенировать и получить разбиение строки [math] s [/math] на меньшее число слов. Получили противоречие. Таким образом доказали даже более сильное утверждение: [math]s = s_1 s_2 ... s_k[/math], [math] k [/math] — минимально [math]\Leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math] 2. Единственность. Пусть существует несколько разбиений [math]s = s_1s_2...s_k = s_1's_2'...s_k'[/math], удовлетворяющих условию теоремы. Сравним длины первых двух слов [math]s_1[/math] и [math]s_1'[/math], если [math]|s_1| = |s_1'|[/math], сравним вторые и так далее. Если длины всех слов одинаковы, то разбиения совпадают — противоречие. Иначе [math]\exists s_i : |s_i| \neq |s_i'|[/math]. Покажем, что такого не может быть: 1) Пусть [math]|s_i| \gt |s_i'|[/math], тогда [math]s_i = s_i's_{i+1}'...t[/math], где [math]t[/math] — префикс [math]s_{j+1}'[/math], [math]i \lt j[/math]. Тогда получаем: [math]s_i \lt t[/math] ([math]s_i[/math] — простая cтрока и по определению меньше своего суффикса) [math]t \lt s_{j+1}'[/math] ([math]t[/math] — префикс [math]s_{j+1}'[/math]) [math]s_{j+1}' \leqslant s_i'[/math] (по условию разбиения) [math]s_i' \lt s_i[/math] (их начало совпадает, и [math]|s_i'| \lt |s_i|[/math] по предположению) Пришли к противоречию: [math]s_i \lt s_i[/math]. 2) Случай [math]|s_i| \lt |s_i'|[/math] симметричен разобранному. То есть не может быть строк [math]s_i[/math] и [math]s_i'[/math] несовпадающей длины, значит, разбиения равны.

[math]\triangleleft[/math]

Алгоритм Дюваля

Алгоритм

Алгоритм Дюваля (англ. Duval's algorithm) находит для данной строки длины [math]n[/math] декомпозицию Линдона за время [math]O(n)[/math] с использованием [math]O(1)[/math] дополнительной памяти. Он строит декомпозицию только на упорядоченных алфавитах.

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

Предпростая строка — строка [math]s[/math], такая что [math]s = ww \dots ww'[/math], где [math]w[/math] — некоторая простая строка, а [math]w'[/math] — некоторый префикс строки [math]w[/math].

Во время работы алгоритма строка [math]s[/math] представляется в виде конкатенации трёх строк [math]s = s_1s_2s_3[/math], где для строки [math]s_1[/math] декомпозиция Линдона уже найдена, и [math]s_1[/math] уже больше не используется алгоритмом; строка [math]s_2[/math] — это предпростая строка; строка [math]s_3[/math] — ещё не обработанная алгоритмом часть строки [math]s[/math]. Алгоритм Дюваля берёт первый символ строки [math]s_3[/math] и пытается дописать его к строке [math]s_2[/math]. При этом, возможно, для какого-то префикса строки [math]s_2[/math] декомпозиция Линдона становится известной, и эта часть переходит к строке [math]s_1[/math].

Будем поддерживать три указателя:

• [math]i[/math] — на начало строки [math]s_2[/math]
• [math]j[/math] — на текущий символ в строке [math]s_2[/math], с которым будет производиться сравнение
• [math]k[/math] — на начало строки [math]s_3[/math]

Внешний цикл алгоритма будет выполняться, пока [math]i \lt n[/math], то есть пока вся строка [math]s[/math] не перейдёт в строку [math]s_1[/math]. Внутри этого цикла создаются два указателя [math] j [/math] и [math] k [/math]. Затем будем пытаться добавить символ [math]s[k][/math] к строке [math]s_2[/math], для чего необходимо произвести сравнение с символом [math]s[j][/math]. При этом будем поддерживать инвариант: [math]k - j[/math] — длина подстроки [math] w [/math].

Возникают три различных случая:

• [math]s[j] = s[k]:[/math] тогда дописывыем символ [math]s[k][/math] к строке [math]s_2[/math] и увеличиваем оба указателя на единицу.
• [math]s[j] \lt s[k]:[/math] тогда строка [math]s_2 + s[k][/math] станет простой. Значит, мы увеличим [math]k[/math] на единицу, а [math]j[/math] передвигаем обратно на [math]i[/math], чтобы следующий символ сравнивался с первым символом [math]s_2[/math]. То есть получаем новую простую строку длины [math]k - j[/math].
• [math]s[j] \gt s[k]:[/math] значит, строка [math]s_2 + s[k][/math] уже не может быть предпростой. Добавляем к [math] s_1 [/math] все строки [math] w [/math], а по нашему инварианту мы знаем, что их длина равна [math] k - j [/math], затем сдвигаем [math] i [/math] к началу позиции строки [math] w' [/math]. После чего внешний цикл запускаем заново:

Реализация

function lyndon(string s, string[] decomposition):
   n [math]\leftarrow[/math] s.length
   i [math]\leftarrow[/math] 0
   cur [math]\leftarrow[/math] 0
   while i [math] \lt  [/math] n
       j [math]\leftarrow[/math] i
       k [math]\leftarrow[/math] i + 1
       while k [math] \lt  [/math] n and s[j] [math] \leqslant [/math] s[k]
           if s[j] [math] \lt  [/math] s[k]
               j [math]\leftarrow[/math] i
           else
               j [math]\leftarrow[/math] k + 1
           k [math]\leftarrow[/math] k + 1
       while i [math]\leqslant[/math] j
           decomposition[cur] [math]\leftarrow[/math] s[i..i + k - j - 1]
           cur [math]\leftarrow[/math] cur + 1
           i [math]\leftarrow[/math] i + k - j

Корректность

Покажем, что алгоритм получает нужное разложение. То есть все [math]s_i[/math] — простые, и [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math] лексикографически.

При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Мы сравниваем символы в [math] w [/math] и [math] w' [/math] на одинаковых позициях, а [math] w' [/math] — префикс [math] w [/math], поэтому инвариант сохраняется.

Во втором случае объединяем все найденные [math]w[/math] с [math]w'[/math] и получем новую строку [math]w''[/math].

Покажем, что [math]w''[/math] является простой. Рассмотрим ее суффикс. Если он начинается в середине [math]w[/math], сравним его посимвольно со строкой [math]s_2[/math], и тогда в каком-то символе он окажется больше [math]s_2[/math], так как суффикс [math] w'' [/math] начинается с [math] u [/math] — суффикса [math]w[/math], а строка [math]w[/math] — простая и по определению меньше всех своих суффиксов. Если суффикс начинается в [math]w'[/math], то при сравнении расхождение будет в символах [math]s[j][/math] и [math]s[k][/math]. Но [math]s[j] \lt s[k][/math], так что суффикс больше [math]w''[/math]. Если же суффикс начинается с первой позиции какой-то подстроки [math]w[/math], то отбросим общий префикс вида [math]ww \dots w[/math] и придем к предыдущему случаю.

В третьем случае просто выведем все [math]w[/math] и продолжим обработку со строки [math]w'[/math], так как при добавлении [math]s[k] [/math], [math]s_2[/math] перестанет удовлетворять требованиям, ведь в этом случае суффикс строки [math] s_2 [/math] равный [math] w'[/math] будет меньше [math]w[/math].

Теперь покажем, что [math]s_i \geqslant s_{i + 1}[/math].

Последоваельность из [math]w[/math] будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с [math]w[/math], а после него будет стоять символ, меньший следующего символа из [math]w[/math] (новое [math]w[/math] получается по третьему случаю), либо следующее слово будет просто префиксом [math] w [/math], и, как следствие, оно будет меньше [math] w [/math] лексикографически.

Асимптотика

Внешний цикл [math]\mathrm{while}[/math] делает не более [math]n[/math] итераций, поскольку в конце каждой его итерации [math] i [/math] увеличивается как минимум на [math] 1 [/math]. Второй внутренний цикл выполнится суммарно не более [math] n [/math], так он добавляет к ответу все символы, причём каждый символ лишь единожды.

Оценим теперь количество итераций первого вложенного цикла [math]\mathrm{while}[/math]. Для этого рассмотрим второй вложенный цикл [math]\mathrm{while}[/math] — он при каждом своём запуске выводит некоторое количество [math]r \geqslant 1[/math] копий одной и той же простой строки некоторой длины [math]p = k - j[/math]. Заметим, что строка [math]s_2[/math] является предпростой, причём её простые строки имеют длину как раз [math]p[/math], то есть её длина не превосходит [math]r \cdot p + p - 1[/math]. Поскольку длина строки [math]s_2[/math] равна [math]k - i[/math], а указатель [math]k[/math] увеличивается на единицу на каждой итерации первого вложенного цикла [math]\mathrm{while}[/math], то этот цикл выполнит не более [math]r \cdot p + p - 2[/math] итераций. Худшим случаем является случай [math]r = 1[/math], и мы получаем, что первый вложенный цикл [math]\mathrm{while}[/math] всякий раз выполняет не менее [math]2p - 2[/math] итераций. Вспоминая, что всего выводится [math]n[/math] символов, получаем, что для вывода [math]n[/math] символов требуется не более [math]2n - 2[/math] итераций первого вложенного [math]\mathrm{while}[/math].

Итого получаем, что итоговая асимптотика алгоритма составляет [math] O(n) [/math].

Отметим, что алгоритму требуется [math] O(1) [/math] памяти: на указатели [math] i, j, k [/math].

Поиск лексикографически минимального суффикса строки

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

Если заметить, что данная нам строка [math]S[/math] является подстрокой заранее данного текста [math]T[/math] длиной [math]n[/math], то выполнив некоторый предподсчёт, мы можем получать значения максимального и минимального суффиксов определённой подстроки гораздо быстрее, чем линейно. Это может быть очень полезным при работе с большими объёмами данных (такими как генетический код и т.д.)

Покажем, что [math]\forall\tau: 1\le\tau\le\log{n}[/math] существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса [math]O(\tau)[/math] и временем препроцессинга [math]O(n\log{n/\tau})[/math] для запросов на нахождение минимального суффикса.

Будем обозначать [math]SA(T)[/math] и [math]ISA(T)[/math] суффиксный массив и инвертированный суффиксный массив строки [math]T[/math] соответственно. Для данных индексов [math]i\lt j[/math] будем обозначать [math]Suf[i,j][/math] массив [math]\{T[i,i+1, \ldots ,|T|-1], \ldots , T[j,j+1, \ldots ,|T|-1]\}[/math]. SA и ISA могут быть улучшены за [math]O(n)[/math], чтобы отвечать на запросы вида

• по данным подстрокам [math]x[/math] и [math]y[/math] строки [math]T[/math] найти [math]lcp(x,y)[/math] и определить, какая из подстрок лексикографически меньше
• по индексам [math]i[/math] и [math]j[/math] вычислить максимальный и минимальный суффикс в [math]Suf[i,j][/math]

Более того, такой улучшенный суффиксный массив может отвечать на запрос "по данным [math]x,y[/math] - подстрокам [math]T[/math] вычислить максимальное чило [math]\alpha[/math], такое, что [math]x^{\alpha}[/math] является префиксом [math]y[/math]" за константное время. Действительно, стоит заметить, что если [math]x[/math] - префикс [math]y = T[i..j][/math], то [math]\alpha |x| \le lcp(T[i..j],T[i+|x|..j] \lt (\alpha+1)|x|)[/math]

Запросы к перевёрнутому улучшенному суфмассиву [math]T^{R}[/math]также имеют смысл. С его помощью мы можем для пары [math]x,y[/math] подстрок [math]T[/math] найти их наибольший общий суффикс [math]lcs(x,y)[/math] и наибольшее число [math]\alpha[/math], такое, что [math]x^{\alpha}[/math] является суффиксом [math]y[/math].

Возьмём строку [math]T[/math] длины [math]n[/math]. Для каждой позиции [math]j[/math] мы выберем O(logN) подстрок [math]T[k..j][/math], которые мы назовём каноническими. Определим как [math]S^{l}_{j}[/math] [math]l[/math]-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции [math]j[/math]. Для пары целых чисел [math]1\le i\lt j\le n[/math] мы определим как [math]\alpha(i,j)[/math] наибольшее [math]l[/math], такое, что [math]S^{l}_{j}[/math] - суффикс [math]T[i..j][/math].

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

• [math]S^{1}_{j} = T[j..j][/math] и для некоторого [math]l=O(logN)[/math] выполняется [math]S^{l}_{j} = T[1..j][/math]
• [math]\forall l:|S^{l+1}_{j}|\le 2|S^{l}_{j}|[/math]
• [math]\alpha(i,j)[/math] и [math]|S^{l}_{j}|[/math] можно вычислить за константное время для данных [math](i,j)[/math] и [math](i,l)[/math] соответственно

Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем [math]|S^{l}_{j}| = \min(2^{l-1}, j)[/math]

Лемма (1):

Минимальный суффикс [math]T[i..j][/math] равен либо [math](a)\ T[p..j][/math], где [math]p[/math]-начальная позиция минимального суффикса в [math]Suf[i,j][/math], либо [math](b)[/math] минимальному суффиксу [math]|S^{\alpha(i,j)}_{j}|[/math]. Более того, [math]p[/math] может быть найдено за константное время с использованием улучшенного суффиксного массива строки [math]T[/math].

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

[math]\triangleright[/math]

По Лемме 1 из 5 минимальный суффикс равен либо [math]T[p..j][/math], либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает [math]\displaystyle \frac{1}{2}|T[p..j]|\leq\frac{1}{2}|T[i..j]|[/math]. С другой стороны, по второму свойству канонических подстрок, длина [math]S_{j}^{\alpha(i,j)}[/math] равна как минимум [math]\displaystyle \frac{1}{2}|T[i..j]|[/math]. Таким образом, во втором случае минимальный суффикс [math]T[i..j][/math] является минимальным суффиксом [math]S_{j}^{\alpha(i,j)}[/math]. Заметим, что для [math]i=j[/math] значения [math]\alpha(i,\ j)[/math] не определены, но тогда выполняется случай [math](a)[/math] из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса [math]Suf [i,\ j][/math] - одна из базовых операций, поддерживаемых улучшенным суфмассивом.

[math]\triangleleft[/math]

Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого [math]j=1,\ \ldots,\ n[/math] содержать битовый вектор [math]B_{j}[/math] длиной [math]\alpha(1,\ j)[/math]. Положим [math]B_{j}[\ell]=1[/math] тогда и только тогда, когда минимальный суффикс [math]S_{j}^{\ell}[/math] длиннее, чем [math]|S_{j}^{\ell-1}|[/math]. Для [math]\ell=1[/math] мы всегда считаем [math]B_{j}[1]=1[/math], поскольку [math]S_{j}^{1}[/math] является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого [math]j[/math] равна [math]\mathcal{O}(\log n)[/math] , поэтому каждый [math]B_{j}[/math] вмещается в константное количество машинных слов и структура данных занимает [math]\mathcal{O}(n)[/math] памяти.

Алгоритм запроса

Предположим, что мы ищем минимальный суффикс [math]T[i..j][/math] c [math]\alpha(i,\ j)=\ell[/math]. Наш подход основан на Лемме 1. Если выполняется случай [math](a)[/math], лемма позволяет нам вычислить ответ за [math]\mathcal{O}(1)[/math]. В общем случае, мы найдём минимальный суффикс [math]S_{j}^{\ell}[/math], сравним его с [math]T[p..j][/math] и вернём меньший из них.

Мы используем Лемму 1 и битовый вектор [math]B_{j}[/math] чтобы посчитать минимальный суффикс [math]S_{j}^{\ell}[/math]. Назовём [math]\ell'[/math] наибольший индекс, не превышающий [math]\ell[/math], такой, что [math]B_{j}[\ell']=1[/math]. Заметим, что такой индекс всегда существует (поскольку[math] B_{j}[1]=1[/math]) и может быть найден за константное время с использованием битовых операций. Для любого индекса [math]\ell''\in\{\ell'+1,\ \ldots,\ \ell\}[/math] мы имеем [math]B_{j}[\ell'']=0[/math], т.е., случай [math](b)[/math] Леммы 1 выполняется для [math]S_{j}^{\ell''}[/math]. Тогда, по индукции, минимальный суффикс [math]S_{j}^{\ell}[/math] на самом деле является минимальным суффиксом [math]S_{j}^{\ell'}[/math]. С другой стороны, [math]B_{j}[\ell']=1[/math], поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс [math]S_{j}^{\ell}[/math] за константное время.

Построение искомой структуры данных

Простой алгоритм построения с временем работы [math]\mathcal{O}(n\log n)[/math] также основывается на Лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти [math]B_{j}[/math] за [math]\mathcal{O}(\log n)[/math]. Мы ищем минимальный суффикс [math]S_{j}^{\ell}[/math] для последовательных значений [math]\ell[/math]. Как только мы получили результат [math]\ell-1[/math], случай [math](a)[/math] Леммы 1 даёт нам второго кандидата на минимальный суффикс [math]S_{j}^{\ell}[/math], и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем [math]B_{j}[\ell]=1[/math] если меньший кандидат не содержится в [math]S_{j}^{\ell-1}[/math]. Стало быть, мы получили следующий результат:

Теорема (2):

Строку [math]T[/math] длины [math]n[/math] можно уместить в структуру данных с [math]\mathcal{O}(n)[/math] памяти, которая позволяет вычислять минимальный суффикс любой подстроки [math]T[/math] за [math]\mathcal{O}(1)[/math]. Эта структура данных может быть построена за [math]\mathcal{O}(n\log n)[/math].

Вышеописанная конструкция проста и работает для любого выбора канонических подстрок, но, к сожалению, она не может быть использована для достижения компромисса между временем запроса и временем построения. Далее мы предложим особый способ выбора канонических подстрок и опишем альтернативный метод построения. Этот способ основывается на предположении, что по данной строке длины [math]k[/math] мы можем найти минимальный суффикс для всех её префиксов за [math]\mathcal{O}(k)[/math]. Следовательно, нам удобно иметь много [math]S_{j}^{\ell}[/math], которые являются префиксами друг друга. Тогда, естественным будет выбрать [math]|S_{j}^{\ell}|=2^{\ell-1}+(j\ mod\ 2^{\ell-1})[/math] , поскольку все подстроки [math]S_{\alpha 2^{l-1}}^{\ell},\ S_{\alpha 2^{l-1}+1}^{\ell},\ \ldots,\ S_{(\alpha+1)2^{l-1}-1}^{\ell}[/math] являются префиксами [math]S_{(\alpha+1)2^{l-1}-1}^{\ell}[/math]. К сожалению, подстроки, выбранные таким способом, не удовлетворяют условию [math]|S_{j}^{\ell}|\leq 2|S_{j}^{\ell-1}|[/math], и, посему, нам необходимо немного изменить его.

Для [math]\ell=1[/math] мы определим [math]S_{j}^{1}=T[j..j][/math]. Для [math]\ell\gt 1[/math] установим [math]m=\lfloor\ell/2\rfloor-1[/math] и определим [math]S_{j}^{\ell}[/math] таким образом: [math] |S_{j}^{\ell}|= \begin{cases} 2 \cdot 2^{m}+(j\ mod\ 2^{m}),& \ell \ mod \ 2 = 0\\ 3 \cdot 2^{m}+(j\ mod\ 2^{m}),& \textup{otherwise} \end{cases}[/math]

Заметим, что если [math]2 \cdot 2^{m}\leq j\lt 3\cdot 2^{m}[/math], то [math]T[1..j]=S_{j}^{2m+2}[/math], в то время как, если [math]3 \cdot 2^{m}\leq j\lt 4\cdot 2^{m}[/math], то [math]T[1..j]=S_{j}^{2m+3}[/math]. Очевидно, что количество таких подстрок, заканчивающихся в [math]j[/math] получается [math]\mathcal{O}(\log n)[/math]. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.

Утверждение (3):

Для любого [math]S_{j}^{\ell}[/math] и [math]S_{j}^{\ell+1}[/math] при [math]\ell\geq 1[/math] мы имеем [math]|S_{j}^{\ell+1}|\lt 2|S_{j}^{\ell}|[/math]

[math]\triangleright[/math]

Для [math]\ell=1[/math] неравенство, очевидно, выполняется. Рассмотрим [math]\ell\geq 2[/math]. Обозначим через [math]m[/math], как и ранее, [math]\lfloor\ell/2\rfloor-1[/math]. Если [math]\ell[/math] чётно, то [math]\ell+1[/math] нечётно и мы имеем [math]|S_{j}^{\ell+1}|=3\cdot 2^{m}+(j\ mod \ 2^{m})\lt 4\cdot 2^{m}\leq 2\cdot(2\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|[/math], в то время как, для нечётного [math]\ell[/math] выполняется [math]|S_{j}^{\ell+1}|=2\cdot 2^{m+1}+(j\ mod \ 2^{m+1})\lt 3\cdot 2^{m+1}\leq 2\cdot(3\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|[/math]

[math]\triangleleft[/math]

Утверждение (4):

Для [math]1\leq i\lt j\leq n[/math], величина [math]\alpha(i,\ j)[/math] может быть посчитана за константное время.

[math]\triangleright[/math]

Положим [math] m=\lfloor\log|T[i..j]|\rfloor[/math]. Заметим, что [math]|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})\lt 2^{m}\leq|T[i..j]|[/math] [math]|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geq 2^{m+1}\gt |T[i..j]|[/math]. Таким образом, [math]\alpha(i,\ j)\in\{2m-1,2m,\ 2m+1\}[/math], и мы можем за константное время проверить, какое из этих трёх значений корректно.

[math]\triangleleft[/math]

После построения улучшенного суфмассива, мы установили все биты[math]B_{j}[1][/math] в 1. После этого, для каждого [math]\ell\gt 1[/math] мы посчитали минимальные суффиксы подстрок [math]S_{j}^{\ell}[/math], как указано далее. Зафиксируем [math]\ell\gt 1[/math] и разобьём [math]T[/math] на куски размером [math]2^{m}[/math](где [math]m=\lfloor\ell/2\rfloor-1[/math]) . Теперь каждый [math]S_{j}^{\ell}[/math] является префиксом конкатенации максимум 4х таких кусков. Вспомним, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля (Алгоритм 3.1 in 6). Разделим [math]T[/math] на куски длиной [math]2^{m}[/math](где [math]m=\lfloor\ell/2\rfloor-1[/math]) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы [math]S_{j}^{\ell}[/math] для всех [math]1\leq j\leq n[/math], за время [math]\mathcal{O}(n)[/math]. Значение [math]B_{j}[\ell][/math] определено с помощью сравнения длины вычисленного минимального суффикса [math]S_{j}^{\ell}[/math] с [math]|S_{j}^{\ell-1}|[/math]. У нас [math]\mathcal{O}(\log n)[/math] фаз алгоритма, что даёт нам время [math]\mathcal{O}(n\log n)[/math] и [math]\mathcal{O}(n)[/math] требуемой памяти.

Компромисс

Чтобы получить структуру данных, со временем построения [math]\mathcal{O}(n\log n/\tau)[/math] и временем запроса [math]\mathcal{O}(\tau)[/math], мы немного по-другому определим битовые вектора. Положим [math]B_{j}[/math] размером [math]\lfloor\alpha(1,\ j)/\tau\rfloor[/math], притом [math]B_{j}[k]=1[/math] тогда и только тогда, когда [math]k=1[/math] или минимальный суффикс [math]S_{j}^{\tau k}[/math] длиннее, чем [math]|S_{j}^{\tau(k-1)}|[/math]. В этом случае, нам необходимо только [math]\mathcal{O}(\log n/\tau)[/math] фаз в алгоритме построения, поэтому он займёт [math]\mathcal{O}(n\log n/\tau)[/math] времени.

Как и ранее, предположим, что мы ищем минимальный суффикс [math]T[i..j][/math], при [math]\alpha(i,\ j)=\ell[/math]. Самое сложное в этом - найти минимальный суффикс [math]S_{j}^{\ell}[/math], и далее необходимо найти [math]\ell'\leq\ell[/math], такой, что минимальный суффикс [math]S_{j}^{\ell}[/math] на самом деле является минимальным суффиксом [math]S_{j}^{\ell'}[/math], но длиннее, чем [math]|S_{j}^{\ell'-1}|[/math]. Если [math]\ell=\tau k[/math] для целого [math]k[/math], мы можем найти наибольший [math]k'\leq k[/math], такой, что [math]B[k']=1[/math], и нам будет известно, что [math]\ell'\in(\tau(k'-1),\ \tau k'][/math]. В общем случае, мы выберем наибольший [math]k[/math], такой что[math]\tau k\leq\ell[/math], и будем знать, что мы должны рассмотреть [math]\ell'\in(\tau k,\ \ell][/math] и [math] \ell'\in(\tau(k'-1),\ \tau k'][/math], где [math]k'[/math] определён, как в предыдущем случае. В результате, мы имеем [math]\mathcal{O}(\tau)[/math] возможных значений [math]\ell'[/math], и нам изестно, что искомый суффикс может быть найден, используя случай [math](a)[/math] Леммы 1 для [math]S_{j}^{\ell'}[/math] для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за [math]\mathcal{O}(\tau)[/math].

Теорема (5):

Для любого [math]1\leq\tau\leq\log n[/math], строка [math]T[/math] длиной [math]n[/math] может храниться в структуре данных, занимающей [math]\mathcal{O}(n)[/math] памяти, позволяющей вычислять минимальный суффикс любой из подстрок [math]T[/math] за время [math]\mathcal{O}(\tau)[/math]. Такая структура данных может быть построена за [math]\mathcal{O}(n\log n/\tau)[/math].

Поиск максимального суффикса

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

Заметим, что единственный компонент из части о минимальном суффиксе, который не может быть сразу адаптирован к задаче о максимальном суффиксе, это Лемма 1. Так как эта лемма неприменима к нашей задаче, далее мы докажем следующую лемму, эквивалентную в смысле алгоритмического приложения. Канонические подстроки [math]S_{j}^{\ell}[/math] обозначены как и ранее.

Лемма (7):

Рассмотрим подстроку [math]T[i..j][/math]. Используя улучшенный суффиксный массив строки [math]T[/math], за [math]\mathcal{O}(1)[/math] можно найти индекс [math]p(i\leq p\leq j)[/math] такой, что максимальный суффикс [math]T[\mu..j][/math] строки [math]T[i..j][/math] равен либо [math](a) T[p..j][/math], либо [math](b)[/math] максимальный суффикс строки [math]S_{j}^{\alpha(i,j)}[/math]

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

[math]\triangleright[/math]

Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора [math]B_{j},\ j\in[1,\ n][/math], с [math]B_{j}[\ell]=1[/math], если [math]\ell=1[/math] или максимальный суффикс строки [math]S_{j}^{\ell}[/math] длиннее [math]|S_{j}^{\ell-1}|[/math]. Алгоритм запроса, описанный в части 4.1, очевидно, может быть адаптирован к нашей задаче, только вместо Леммы 1 мы будем использовать Лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:

[math]\triangleleft[/math]

Теорема (8):

Строка [math]T[/math] длины [math]n[/math] может храниться в структуре данных с [math]\mathcal{O}(n)[/math] памяти, которая позволяет вычислять максимальный суффикс любой подстроки строки [math]T[/math] за время [math]\mathcal{O}(1)[/math].

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

[math]\triangleright[/math]

Алгоритмы построения за [math]\mathcal{O}(n\log n)[/math] и компромисс между временем запросов и временем построения, описанные в секциях 4.2 и 4.3, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения [math]\mathcal{O}(n)[/math], как будет показано в секции 5.2.

[math]\triangleleft[/math]

Доказательство леммы 7

Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию [math]p\in[i,\ j][/math].

Заметим, что если максимальный суффикс [math]T[\mu..j][/math] of [math]T[i..j][/math] короче, чем [math]S_{j}^{\alpha(i,j)}[/math] (случай (b) Леммы 7), алгоритм может вернуть любое [math]p\in[i,\ j][/math]. Далее мы предполагаем, что [math]T[\mu..j][/math] длиннее, чем [math]S_{j}^{\alpha(i,j)}[/math] и показываем, что при этом предположении алгоритм вернёт [math] p=\mu[/math]. Из нашего предположения свойств канонических подстрок следует, что [math]\mu\in[i,\ r][/math], where [math]r=j-|S_{j}^{\alpha(i,j)}|[/math], и что длины суффиксов подстроки [math]T[i..j][/math], начинающихся с позиций в промежутке [math][i,\ r][/math], отличаются не более чем в два раза.

Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в 1

Лемма (9):

Пусть [math]P_{1}=T[p_{1}..j][/math] — префикс строки [math]T[\mu..j][/math] и пусть [math]P_{2}=T[p_{2}..j][/math], где [math]T[p_{2}..j][/math] — максимальный суффикс в [math]Suf [i,p_{1}-1][/math]. Если [math]P_{1}[/math] не является префиксом [math]P_{2}[/math], тогда [math]\mu=p_{1}[/math]. Иначе, [math]P_{2}[/math] также является префиксом строки [math]T[\mu..j][/math].

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

[math]\triangleright[/math]

Пусть [math]T[p_{1}..][/math] — максимальный суффикс в [math]Suf [i,\ r][/math] и [math]T[p_{2}..][/math] — максимальный суффикс в [math]Suf [i,\ p_{1}-1][/math]. Очевидно, [math]P_{1}=T[p_{1}..j][/math] является префиксом строки [math]T[\mu..j][/math]. Предположим, что [math]P_{1}[/math] — префикс (иначе [math]P_{2} \ p_{1}=\mu\[/math] по Лемме 9). Длины [math]P_{1}[/math] и [math]P_{2}[/math] различаются не более чем в два раза, поэтому [math]2|P_{1}|\geq|P_{2}|[/math]. Благодаря этому, [math]P_{1}[/math] и [math]P_{2}[/math] имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из 1, но здесь мы приводим доказательства вследствие другого обозначения.

[math]\triangleleft[/math]

Лемма (10):

Подстрока [math]\rho=T[p_{2}..p_{1}-1][/math] — минимальный период строки [math]P_{2}[/math], т.е. [math]\rho[/math] — кратчайшая строка, такая, что для какого-то [math]s\geq 1[/math] выполняется [math]P_{2}=\rho^{s}\rho'[/math].

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

[math]\triangleright[/math]

Поскольку [math]P_{1}[/math] — бордер [math]P_{2},\ \rho=T[p_{2}..p_{1}-1][/math] — период [math]P_{2}[/math]. Остается лишь доказать, что невозможно найти более короткий период. Таким образом, рассмотрим(consider) кратчайший период [math]\gamma[/math], и предположим, что [math]|\gamma|\lt |\rho|[/math]. Тогда [math]|\gamma|+|\rho|\leq 2|\rho|\leq|T[p_{2}..j]|[/math], и по лемме о периодичности подстрока [math]P_{2}[/math] имеет другой период [math]\mathrm{g}\mathrm{c}\mathrm{d}(|\gamma|,\ |\rho|)[/math] . Так как [math]\gamma[/math] — кратчайший период, то [math]|\rho|[/math] должно быть степенью [math]|\gamma|[/math], т.е. [math]\rho=\gamma^{k}[/math] для какого-то [math]k\geq 2[/math]. Предположим, что [math]T[p_{1}..]\prec\gamma T[p_{1}..][/math]. Тогда приписывание к обеим частям последнего неравенства степеней [math]\gamma[/math] даёт [math]\gamma^{\ell-1}T[p_{1}..]\prec\gamma^{\ell}T[p_{1}..][/math] для любого [math]1\leq\ell\leq k[/math], таким образом из транзитивности [math]\prec[/math] получаем [math]T[p_{1}..]\prec\gamma^{k}T[p_{1}..]=T[p_{2}..][/math], что противоречит максимальности [math]T[p_{1}..][/math] in [math]Suf[i,\ r][/math]. Таким образом, [math]T[p_{1}..]\succ\gamma T[p_{1}..][/math], и следовательно [math]\gamma^{k-1}T[p_{1}..]\succ\gamma^{k}T[p_{1}..][/math]. Но [math]\gamma^{k-1}T[p_{1}..]=T[p_{2}+|\gamma|..][/math] и [math]\gamma^{k}T[p_{1}..]=T[p_{2}..][/math], поэтому [math]T[p_{2}+|\gamma|..][/math] больше, чем [math]T[p_{2}..][/math] и принадлежит [math]Suf [i,\ p_{1}-1][/math], противоречие. Заметим, что на самом деле [math]s\geq 2[/math], потому что [math]2|P_{1}|\geq|P_{2}|=|P_{1}|+|\rho|[/math], поэтому [math]|P_{1}|\geq|\rho|.\ [/math]

[math]\triangleleft[/math]

Лемма (11):

Положим, [math]P_{2}=\rho P_{1}=\rho^{s}\rho'[/math]. Тогда максимальный суффикс [math]T[\mu..j][/math] — длиннейший суффикс строки [math]T[i..j][/math] равен [math]\rho^{t}\rho'[/math] для некоторого [math]t[/math]. (См. рисунок 1)

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

[math]\triangleright[/math]

Очевидно, что [math]P_{2}[/math] является бордером [math]T[\mu..j][/math]. Из [math]P_{2}=\rho P_{1}[/math] и [math]|T[\mu..j]|\leq 2|P_{1}|[/math] имеем [math]|T[\mu..j]|+|\rho|\leq 2|P_{1}|+\rho\leq 2|P_{2}|[/math]. Следовательно вхождения [math]P_{2}[/math] в качестве префикса и в качестве суффикса строки [math]T[\mu..j][/math] перекрывают друг друга как минимум в [math]|\rho|[/math] позициях. Т.к. [math]|\rho|[/math] — период [math]P_{2}[/math], отсюда следует, что [math]|\rho|[/math] также является периодом [math]T[\mu..j][/math]. Таким образом, [math]T[\mu..j]=\rho''\rho^{r}\rho'[/math], где [math]r[/math] — целое число и [math]\rho''[/math] — суффикс [math]\rho[/math]. Более того, [math]\rho^{2}[/math] — это префикс [math]T[\mu..j][/math], поскольку является префиксом [math]P_{2}[/math], который в свою очередь является префиксом [math]T[\mu..j][/math]. Теперь [math]\rho''\neq\xi j[/math] будет означать нетривиальное вхождение [math]\rho[/math] в [math]\rho^{2}[/math], которое противоречит примитивности [math]\rho[/math], смотри 4. Таким образом, [math]T[\mu..j]=\rho^{r}\rho'[/math]. Если [math]t\gt r[/math], тогда [math]\rho^{t}\rho'\succ\rho^{r}\rho'[/math], поэтому [math]T[\mu..j][/math] — длиннейший суффикс строки [math]T[i..j][/math], равный [math]\rho^{t}\rho'[/math] для некоторого [math]t[/math].

[math]\triangleleft[/math]

Доказательство леммы 7

[math]\triangleright[/math]

Пусть [math]T[p_{1}..][/math] — максимальный суффикс в [math]Suf [i,\ r][/math] и [math]T[p_{2}..][/math] — максимальный суффикс в [math]Suf [i,p_{1}-1][/math]. Сначала вычислим [math]p_{1}[/math] и [math]p_{2}[/math] за [math]\mathcal{O}(1)[/math], используя улучшенный суффиксный массив. Затем проверим, что [math]T[p_{1}..j][/math] является префиксом [math]T[p_{2}..j][/math]. Если это неверно, то мы возвращаем [math]p=p_{1}[/math]. Иначе, мы вычисляем максимальное целое число [math]r[/math], такое, что [math]\rho^{r}[/math] (для [math]\rho=T[p_{2}..p_{1}-1])[/math]) — суффикс [math]T[i..p_{1}-1][/math], используя метод из алгоритма поиска минимального суффикса, и возвращаем [math]p=p_{1}-r|\rho|[/math]. Из вышеописанных лемм следует, что если [math]T[\mu..j][/math] длиннее [math]S_{j}^{\alpha(i,j)}[/math], тогда [math] p=\mu[/math].

[math]\triangleleft[/math]

Построение

Наш алгоритм основывается на следующем понятии. Для [math]1\leq p\leq j\leq n[/math] мы говорим, что позиция [math]p[/math] [math]j[/math]-активна, если не существует такой позиции [math]p'\in\{p+1,\ \ldots,\ j\}[/math], что [math]T[p'..j]\succ T[p..j][/math]. Другими словами, [math]p[/math] — [math]j[/math]-активна тогда и только тогда, когда [math]T[p..j][/math] — максимальный суффикс самого себя. Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки [math]T[i..j][/math] — это минимальная [math]j[/math]-активная позиция в промежутке [math][i,\ j][/math]. Следовательно, при [math]\ell\gt 1[/math] мы имеем [math]B_{j}[\ell]=1[/math] тогда и только тогда, когда существует как минимум одна [math]j[/math]-активная позиция в диапазоне [math]R_{j}^{\ell}=[j-|S_{j}^{\ell}|+1, j-|S_{j}^{\ell-1}|][/math]. Положим [math]R_{j}^{1}=[j,\ j][/math], тогда это равенство также сохраняется для [math]\ell=1[/math] (поскольку [math]j[/math] всегда [math]j[/math]-активна)

Пример: Если [math]T[1..8]=dcccabab[/math], то 8-активными позициями будут 1, 2, 3, 4, 6, 8.

Алгоритм построения перебирает [math]j[/math] от 1 до [math]n[/math], сохраняя список активных позиций и вычисляя битовые вектора [math]B_{j}[/math]. Мы также сохраняем диапазоны [math]R_{j}^{\ell}[/math] для выбора канонических подстрок, описанных в пункте 4.2, которые образуют разбиение [math][[/math]1, [math]j][/math]. Два следующих результата описывают изменения списка [math]j[/math]-активных позиций и диапазонов [math]R_{j}^{\ell}[/math], когда мы увеличиваем [math]j[/math].

Лемма (13):

Если список всех [math](j-1)[/math]-активных позиций состоит из [math]p_{1}\lt p_{2}\lt [/math] . . . [math]\lt p_{k}[/math], то список [math]j[/math]-активных позиций может быть создан путём добавления [math]j[/math], и повторения следующей процедуры: если [math]p_{\ell}[/math] и [math]p_{\ell+1}[/math] — два соседа в текущем списке и [math]T[j]\neq T[j+p_{\ell}-p_{\ell+1}][/math], удаляем [math]p_{\ell}[/math] или [math]p_{\ell+1}[/math] из списка, зависимо от того, что [math]T[j]\gt T[j+p_{\ell}-p_{\ell+1}][/math] или [math]T[j]\lt T[j+p_{\ell}-p_{\ell+1}][/math], соответственно.

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

[math]\triangleright[/math]

Сначала мы докажем, что если позиция [math]1\leq p\leq j-1[/math] не является [math](j-1)[/math]-активной, то она также не является и [math]j[/math]-активной. Действительно, если [math]p[/math] не [math](j-1)[/math]-активна, тогда по определению существует позиция [math]p\lt p'\leq j-1[/math], такая, что [math]T[p..j-1]\prec T[p'..j-1][/math]. Следовательно, [math]T[p..j]=T[p..j-1]T[j]\prec T[p'..j-1]T[j]=T[p'..j][/math] и [math]p[/math] не является [math]j[/math]-активной. Отсюда, единственными кандидатами на [math]j[/math]-активные позиции остаются [math](j-1)[/math]-активные позиции и [math]j[/math]. Далее, заметим, что если [math]1\leq p\leq j-1[/math] — [math]\mathrm{a}(j-1)[/math]-активная позиция и [math]T[p'..j-1][/math] — префикс [math]T[p..j-1][/math], то [math]p'[/math] тоже является [math](j-1)[/math]-активной. Если это не так, тогда существует позиция [math]p'',\ p'\lt p''\lt j-1[/math], такая, что [math]T[p'..j-1]\prec T[p''..j-1][/math], и из этого следует, что [math]T[p..j-1]=T[p'..j-1]T[j+p-p'..j-1]\prec T[p''..j-1][/math], противоречие. [math]\mathrm{A}(j-1)[/math]-активная позиция [math]p[/math] не является [math]j[/math]-активной только если (1) [math]T[j]\geq T[p][/math] или (2) существует [math]p\lt p'\leq j-1[/math] такая, что [math]T[p'..j-1][/math] — префикс [math]T[p..j-1][/math], т.е. [math]p'[/math] — [math](j-1)[/math]-активна и [math]T[p'..j]\succ T[p..j][/math] или, другими словами, [math]T[j]\gt T[j+p-p'][/math]. Оба этих случая выявляются процедурой удаления.

[math]\triangleleft[/math]

Пример: Если [math]T[1..9]=dcccababb[/math], то 8-активными позициями будут: 1, 2, 3, 4, 6, 8, и 9-активными позициями будут: 1, 2, 3, 4, 8, 9, т.е. мы добавляем 9 в наш список 8-активных позиций, а затем удаляем 6.

Ссылки

• Wikipedia — Lyndon word
• MAXimal :: algo :: Декомпозиция Линдона. Алгоритм Дюваля
• Algebras, Rings, and Modules: Lie Algebras and Hopf Algebras", Michiel Hazewinkel, Nadezhda Mikhaĭlovna Gubareni, Vladimir V. Kirichenko, страница 242
• Computing minimal and maximal suffixes of a substring revisited
• M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007
• On Minimal and Maximal Suffixes of a Substring
• Factorizing words over an ordered alphabet