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

Декомпозиция Линдона была изобретена Роджером Линдоном (англ. 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 \ldots s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \geqslant s_2 \geqslant \ldots\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]s[/math] является префиксом [math]t[/math], тогда: [math]s + t = s + s + x[/math] [math]s + s + x \lt s + x[/math] [math]s + x \lt x[/math] Следовательно [math]t \lt [/math] любого суффикса [math]t[/math] (так как по условию [math]t[/math] явлеяется простой строкой), либо [math]\exists i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i[/math]. Из обоих ситуаций следует, что [math] 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 \ldots s_k[/math], [math] k [/math] — минимально [math]\Leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math] 2. Единственность. Пусть существует несколько разбиений [math]s = s_1s_2 \ldots s_k = s_1's_2' \ldots 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}' \ldots 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 \ldots \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\leqslant\tau\log{n}[/math] существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса [math]O(\tau)[/math] и временем препроцессинга [math]O(n\log{n/\tau})[/math] для запросов на нахождение минимального суффикса.

Для данных индексов [math]i\lt j[/math] будем обозначать как [math]Suf[i,j][/math] массив [math]\{T[i\ldots], \ldots , T[j\ldots]\}[/math] - подмассив с индекса [math]i[/math] по [math]j[/math] массива всех суффиксов строки. Множество всех непустых суффиксов строки [math]Suf[1,|T|][/math] будем обозначать для краткости как [math]Suf[/math]. Также, будем обозначать [math]SA(T)[/math] и [math]ISA(T)[/math] суффиксный массив и инвертированный суффиксный массив строки [math]T[/math] соответственно. [math]SA[/math] и [math]ISA[/math] могут быть улучшены за [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 \ldots j][/math], то [math]\alpha |x| \leqslant lcp(T[i \ldots j],T[i+|x| \ldots 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] мы выберем [math]O(\log{N})[/math] подстрок [math]T[k \ldots j][/math], которые мы назовём каноническими. Определим как [math]S^{l}_{j}[/math] [math]l[/math]-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции [math]j[/math]. Для пары целых чисел [math]1\leqslant i\lt j\leqslant n[/math] мы определим как [math]\alpha(i,j)[/math] наибольшее [math]l[/math], такое, что [math]S^{l}_{j}[/math] — суффикс [math]T[i \ldots j][/math].

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

• [math]S^{1}_{j} = T[j \ldots j][/math] и для некоторого [math]l=O(\log{N})[/math] выполняется [math]S^{l}_{j} = T[1 \ldots j][/math]
• [math]\forall l:|S^{l+1}_{j}|\leqslant 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]

Лемма (0):

Пусть [math]T[\mu \ldots j][/math] - искомый лексикографически наименьший суффикс. Если у [math]T[m \ldots j][/math] нет непустых бордеров, то [math]T[\mu \ldots j] = T[m \ldots j][/math]. Иначе [math]T[\mu \ldots j][/math] — кратчайший непустой бордер [math]T[m \ldots j][/math].

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

[math]\triangleright[/math]

Покажем, что [math]T[\mu \ldots j][/math] является одновременно префиксом и суффиксом [math]T[m \ldots j][/math]. Если [math]T[m \ldots j]=T[\mu \ldots j][/math], то лемма доказана, иначе [math]T[\mu \ldots j]\prec T[m \ldots j][/math]. По определению лексикографического порядка, либо [math](1)[/math] [math]T[\mu \ldots j][/math] является префиксом [math]T[m \ldots j][/math], либо [math](2)[/math] существует [math]\displaystyle \ell\lt \min(|T[\mu \ldots j]|,\ |T[m \ldots j]|)[/math] такой, что [math]T[\mu \ldots \mu+ \ell]=T[m \ldots m+\ell][/math], и [math]T[\mu+\ell+1]\lt T[m+\ell+1][/math]. В случае [math](1)[/math] выполняется [math] m\lt \mu[/math] и таким образом [math]T[\mu \ldots j][/math] также является суффиксом [math]T[m \ldots j][/math]. Покажем, что второй случай никогда не выполняется. Действительно, [math]T[\mu \ldots ]\prec T[m \ldots ][/math], но в [math]Suf [i,\ j][/math] [math]T[m \ldots ][/math] является лексикографически наименьшим суффиксом. Следовательно, [math]T[\mu \ldots j][/math] является одновременно префиксом и суффиксом [math]T[m \ldots j][/math]. Если [math]T[m \ldots j][/math] не имеет непустых бордеров, то [math]\mu=m[/math]. Иначе, [math]T[\mu \ldots j][/math] является бордером [math]T[m \ldots j][/math]. Предположим, [math]T[\mu \ldots j][/math] - не наименьший непустой бордер [math]T[m \ldots j][/math], тогда существует более короткий бордер [math]\beta[/math]. По определению, [math]\beta[/math] — префикс [math]T[m \ldots j][/math], следовательно он также является префиксом [math]T[\mu \ldots j][/math]. Следовательно, [math]\beta\prec T[\mu \ldots j][/math], что приводит нас к противоречию.

[math]\triangleleft[/math]

Лемма (1):

Минимальный суффикс [math]T[i \ldots j][/math] равен либо [math](a)\ T[p \ldots 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]

По лемме 0 минимальный суффикс равен либо [math]T[p \ldots j][/math], либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает [math]\displaystyle \frac{1}{2}|T[p \ldots j]|\leqslant\frac{1}{2}|T[i \ldots j]|[/math]. С другой стороны, по второму свойству канонических подстрок, длина [math]S_{j}^{\alpha(i,j)}[/math] равна как минимум [math]\displaystyle \frac{1}{2}|T[i \ldots j]|[/math]. Таким образом, во втором случае минимальный суффикс [math]T[i \ldots 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 \ldots 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 \ldots 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}|\leqslant 2|S_{j}^{\ell-1}|[/math], и, посему, нам необходимо немного изменить его.

Для [math]\ell=1[/math] мы определим [math]S_{j}^{1}=T[j \ldots 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}\leqslant j\lt 3\cdot 2^{m}[/math], то [math]T[1 \ldots j]=S_{j}^{2m+2}[/math], в то время как, если [math]3 \cdot 2^{m}\leqslant j\lt 4\cdot 2^{m}[/math], то [math]T[1 \ldots 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\geqslant 1[/math] мы имеем [math]|S_{j}^{\ell+1}|\lt 2|S_{j}^{\ell}|[/math]

[math]\triangleright[/math]

Для [math]\ell=1[/math] неравенство, очевидно, выполняется. Рассмотрим [math]\ell\geqslant 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}\leqslant 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}\leqslant 2\cdot(3\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|[/math]

[math]\triangleleft[/math]

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

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

[math]\triangleright[/math]

Положим [math] m=\lfloor\log|T[i \ldots j]|\rfloor[/math]. Заметим, что [math]|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})\lt 2^{m}\leqslant|T[i \ldots j]|[/math] [math]|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geqslant 2^{m+1}\gt |T[i \ldots 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х таких кусков. Известно, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля. Разделим [math]T[/math] на куски длиной [math]2^{m}[/math](где [math]m=\lfloor\ell/2\rfloor-1[/math]) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы [math]S_{j}^{\ell}[/math] для всех [math]1\leqslant j\leqslant 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 \ldots j][/math], при [math]\alpha(i,\ j)=\ell[/math]. Самое сложное в этом — найти минимальный суффикс [math]S_{j}^{\ell}[/math], и далее необходимо найти [math]\ell'\leqslant\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'\leqslant k[/math], такой, что [math]B[k']=1[/math], и нам будет известно, что [math]\ell'\in(\tau(k'-1),\ \tau k'][/math]. В общем случае, мы выберем наибольший [math]k[/math], такой что [math]\tau k\leqslant\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\leqslant\tau\leqslant\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 \ldots j][/math]. Используя улучшенный суффиксный массив строки [math]T[/math], за [math]\mathcal{O}(1)[/math] времени можно найти такой индекс [math]p\ (i\leqslant p\leqslant j)[/math], что максимальный суффикс [math]T[\mu \ldots j][/math] строки [math]T[i \ldots j][/math] равен либо [math](a) T[p \ldots j][/math], либо [math](b)[/math] максимальному суффиксу строки [math]S_{j}^{\alpha(i,j)}[/math]

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

[math]\triangleright[/math]

Доказательство приводится ниже, с использованием вспомогательных лемм.

[math]\triangleleft[/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]. Алгоритм запроса, описанный здесь, очевидно, может быть адаптирован к нашей задаче, только вместо леммы 1 мы будем использовать лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:

Теорема (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] и компромисс между временем запросов и временем построения, описанные здесь и здесь соответственно, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения [math]\mathcal{O}(n)[/math], как будет показано ниже.

[math]\triangleleft[/math]

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

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

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

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

Лемма (9):

Пусть [math]P_{1}=T[p_{1} \ldots j][/math] — префикс строки [math]T[\mu \ldots j][/math] и пусть [math]P_{2}=T[p_{2} \ldots j][/math], где [math]T[p_{2} \ldots 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 \ldots j][/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма (10):

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма (11):

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Наш алгоритм основывается на следующем понятии. Для [math]1\leqslant p\leqslant j\leqslant n[/math] мы говорим, что позиция [math]p[/math] [math]j[/math]-активна, если не существует такой позиции [math]p'\in\{p+1,\ \ldots,\ j\}[/math], что [math]T[p' \ldots j]\succ T[p \ldots j][/math]. Другими словами, [math]p[/math] — [math]j[/math]-активна тогда и только тогда, когда [math]T[p \ldots j][/math] — максимальный суффикс самого себя. Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки [math]T[i \ldots 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]-активна)

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

Алгоритм построения перебирает [math]j[/math] от [math]1[/math] до [math]n[/math], сохраняя список активных позиций и вычисляя битовые вектора [math]B_{j}[/math]. Мы также сохраняем диапазоны [math]R_{j}^{\ell}[/math] для выбора канонических подстрок, описанных здесь, которые образуют разбиение [math][1,\ 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\leqslant p\leqslant j-1[/math] не является [math](j-1)[/math]-активной, то она также не является и [math]j[/math]-активной. Действительно, если [math]p[/math] не [math](j-1)[/math]-активна, тогда по определению существует позиция [math]p\lt p'\leqslant j-1[/math], такая, что [math]T[p \ldots j-1]\prec T[p' \ldots j-1][/math]. Следовательно, [math]T[p \ldots j]=T[p \ldots j-1]T[j]\prec T[p' \ldots j-1]T[j]=T[p' \ldots j][/math] и [math]p[/math] не является [math]j[/math]-активной. Отсюда, единственными кандидатами на [math]j[/math]-активные позиции остаются [math](j-1)[/math]-активные позиции и [math]j[/math]. Далее, заметим, что если [math]1\leqslant p\leqslant j-1[/math] — [math]\mathrm{a}(j-1)[/math]-активная позиция и [math]T[p' \ldots j-1][/math] — префикс [math]T[p \ldots j-1][/math], то [math]p'[/math] тоже является [math](j-1)[/math]-активной. Если это не так, тогда существует позиция [math]p'',\ p'\lt p''\lt j-1[/math], такая, что [math]T[p' \ldots j-1]\prec T[p'' \ldots j-1][/math], и из этого следует, что [math]T[p \ldots j-1]=T[p' \ldots j-1]T[j+p-p' \ldots j-1]\prec T[p'' \ldots j-1][/math], противоречие. [math]\mathrm{A}(j-1)[/math]-активная позиция [math]p[/math] не является [math]j[/math]-активной только если (1) [math]T[j]\geqslant T[p][/math] или (2) существует [math]p\lt p'\leqslant j-1[/math] такая, что [math]T[p' \ldots j-1][/math] — префикс [math]T[p \ldots j-1][/math], т.е. [math]p'[/math] — [math](j-1)[/math]-активна и [math]T[p' \ldots j]\succ T[p \ldots j][/math] или, другими словами, [math]T[j]\gt T[j+p-p'][/math]. Оба этих случая выявляются процедурой удаления.

[math]\triangleleft[/math]

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

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

Пусть [math]j\in[1,\ n][/math] и предположим, что [math]2^{k}[/math] — максимальная степень двойки, которой кратно [math]j[/math]. [math](a)[/math] Если [math]\ell=1[/math], то [math]R_{j}^{\ell}=[j,\ j][/math]. [math](b)[/math] Если [math]2\leqslant\ell\lt 2k+4[/math], то [math]R_{j}^{\ell}=R_{j-1}^{\ell-1}[/math]. [math](c)[/math] Если [math]\ell=2k+4[/math], то [math]R_{j}^{\ell}=R_{j-1}^{\ell}\cup R_{j-1}^{\ell-1}[/math]. [math](d)[/math] Если [math]\ell\gt 2k+4[/math], то [math]R_{j}^{\ell}=R_{j-1}^{\ell}[/math].

[math]\triangleright[/math]

Заметим, что у нас есть [math]R_{j}^{1}=[j,\ j][/math] и [math]R_{j}^{2}=[j-1,\ j-1][/math], в то время как для [math]\ell\gt 2[/math] [math]\ell\gt 2 R_{j}^{\ell}=\left\{\begin{array}{ll} [2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)+1,\ 2^{m-1}(\lfloor\frac{j}{2^{m-1}}\rfloor-3)] & \mathrm{i}\mathrm{f}\ \ell\ \mathrm{i}\mathrm{s}\ \mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n},\\ {[}2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-3)+1,\ 2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)] & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}, \end{array}\right.[/math] где [math]m=\lfloor\ell/2\rfloor-1[/math]. Также заметим, что [math]2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-3)=\left\{\begin{array}{l} 2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2)\ \mathrm{i}\mathrm{f}\ 2^{m}|j\\ 2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-3)\ \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}, \end{array}\right.[/math] [math]2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-2)=\left\{\begin{array}{ll} 2^{m-1}(\lfloor\frac{j-1}{2^{m-1}}\rfloor-3) & \mathrm{i}\mathrm{f}\ 2^{m}|j\\ 2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2) & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}. \end{array}\right.[/math] Более того, [math]2^{m}|j\Leftrightarrow\ell\leqslant 2k+3[/math] и [math]2^{m-1}|j\Leftrightarrow\ell\leqslant 2k+5[/math], что упрощает проверку заявленных формул. Заметим, что возможно, что [math]R_{j}^{\ell}[/math] определено только для значений [math]\ell[/math], меньших, чем [math]2k+4[/math]. Это именно тот случай, когда число диапазонов растёт на единицу, иначе оно остается неизменным.

[math]\triangleleft[/math]

Рис. 2 Разбиения [math][1,\ j][/math] на [math]R_{j}^{\ell}[/math] при [math]j=27[/math] и [math]j=28[/math]. При [math]j=28[/math], [math]k=2[/math] и [math]2k+4=8,\ R_{27}^{7}[/math] и [math]R_{27}^{8}[/math] объединяются в [math]R_{28}^{8}[/math]. На самом деле, все длины [math]|R_{j}^{\ell}|[/math] являются степенями двойки, но наш алгоритм не использует это наблюдение.

Мы просматриваем позиции строки [math]T[/math] слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение [math][1,\ j][/math] на диапазоны [math]R_{j}^{\ell}[/math]. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что [math]B_{j}[\ell]=1[/math] только когда [math]l[/math]-й счетчик не равен нулю. Чтобы эффективно обновить список [math](j-1)[/math]-активных позиций и получить список [math]j[/math]-активных позиций, мы также храним для каждого [math]j'[/math] список указателей на пары соседних позиций, таких, что одна из них должна быть удалена, когда мы достигнем [math]j=j'[/math]. Всякий раз когда появляется новая пара соседних позиций [math]p_{z},\ p_{z+1}[/math], мы считаем [math]L=[/math] [math]lcp[/math] [math](T[p_{z} \ldots],\ T[p_{z+1} \ldots])[/math] и с этого момента наименьший [math]j'=p_{z}+L[/math], когда одна из них должна быть удалена из списка, и вставляем указатель на пару [math]p_{z},\ p_{z+1}[/math] в [math]j'[/math]-й список. Когда мы действительно достигнем [math]j=j'[/math], мы проследуем по указателю и проверим, что [math]p_{\ell}[/math] и [math]p_{\ell+1}[/math] по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем. Из леммы 13 следует, что два возможных обновления списка при переходе от [math]j-1[/math] к [math]j[/math] добавляют [math]j[/math] или удаляют какую-то позицию из списка. Это гарантирует, что процесс удаления из леммы 13 и процесс, который мы описали, эквивалентны.

Предположим, что мы уже знаем список [math](j-1)[/math]-активных позиций, битовый вектор [math]B_{j-1}[/math], и число [math](j-1)[/math]-активных позиций в каждом диапазоне [math]R_{j-1}^{\ell}[/math]. Сначала мы обновим список [math](j-1)[/math]-активных позиций. Когда позиция удалена из списка, мы находим диапазон, к которому она принадлежит и уменьшаем его счетчик внутренних позиций. Если счетчик становится нулевым, мы очищаем соответствующий бит битового вектора. Далее мы начинаем обновлять разбиение: сначала мы добавляем новый диапазон [math][j,\ j][/math] к разбиению [math][1 \ldots j-1][/math] и инициализируем счетчик активных позиций единицей. Затем, мы обновлям первые [math]2k+4[/math] диапазонов ([math]k[/math] — максимальная степень [math]2[/math], которой кратно [math]j[/math]), используя теорему 15, а также счетчики и битовый вектор. Этот процесс займет [math]\mathcal{O}(k)[/math] времени, что амортизированно составляет [math]\displaystyle \mathcal{O}(\sum_{k=1}^{\infty}\frac{k}{2^{k}})=\mathcal{O}(1)[/math] при всех значениях [math]j[/math].

Из вышеописанного следует теорема:

Теорема (16):

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

См. также

• Алгоритм Крочемора
• Суффиксный массив
• Алгоритм цифровой сортировки суффиксов циклической строки

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

• 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