1632
правки
Изменения
м
Будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> суффиксный массив и инвертированный суффиксный массив строки <tex>T</tex> соответственно. Для данных индексов <tex>i<j</tex> будем обозначать как <tex>Suf[i,j]</tex> массив <tex>\{T[i,i+1, \ldots ,|T|-1], \ldots , T[j,\ldots]\}</tex> - подмассив с индекса <tex>i</tex> по <tex>j+</tex> массива всех суффиксов строки. Множество всех непустых суффиксов строки <tex>Suf[1, \ldots ,|T|-1]\}</tex>будем обозначать для краткости как <tex>Suf</tex>. Также, будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> [[суффиксный массив]] и инвертированный суффиксный массив строки <tex>T</tex> соответственно. <tex>SA</tex> и <tex>ISA</tex> могут быть улучшены за <tex>O(n)</tex>, чтобы отвечать на запросы вида * по данным подстрокам <tex>x</tex> и <tex>y</tex> строки <tex>T</tex> найти [[Алгоритм Касаи и др.| наибольший общий префикс]] <tex>lcp(x,y)</tex> и определить, какая из подстрок лексикографически меньше
*[http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 On Minimal and Maximal Suffixes of a Substring]
*[http://www.sciencedirect.com/science/article/pii/0196677483900172 Factorizing words over an ordered alphabet]
*[http://www.google.ru/books?hl=en&lr=&id=PuOOY_DR55UC&oi=fnd&pg=PR7&dq=M.+Crochemore,+C.+Hancart,+and+T.+Lecroq.+Algorithms+on+Strings.+Cambridge+University+Press,+2007&ots=oe_VacDwgA&sig=PKoDRn6K6nZsWfajL0-0jkSlAf8&redir_esc=y#v=onepage&q&f=false M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007]
rollbackEdits.php mass rollback
{{Определение
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего собственного суффикса.
}}
{{Определение
|id=def2.
|definition='''Декомпозиция Линдона''' (англ. ''Lyndon decomposition'') строки <tex>s</tex> {{---}} её разложение <tex>s = s_1s_2...\ldots s_k</tex>, где строки <tex>s_i</tex> просты, и при этом <tex>s_1 \geqslant s_2 \geqslant ... \ldots\geqslant s_k</tex>.
}}
2. <tex>s + t</tex> {{---}} простая
|proof=
1. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, тогда: <tex>s + t = s + s + x</tex> <tex>s + s + x < s + x</tex> <tex>s + x < x</tex> Следовательно <tex>t <</tex> любого суффикса <tex>t</tex> (так как по условию <tex>t</tex> явлеяется простой строкой), либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow </tex>. Из обоих ситуаций следует, что <tex> s + t < t</tex>
2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:
* <tex>|u| = |t| \Rightarrow u = t \Rightarrow u > s + t</tex> по пункту 1
* <tex>|u| < |t| \Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \Rightarrow s + t < t < u</tex>
* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше больше самой строки <tex> s </tex> в каком-то символе, значит, <tex> s + t < s'' + t</tex>
}}
Предположим, что это не так. Значит, <tex>\exists i : s_i < s_{i+1}</tex>. Так как слова <tex> s_i </tex> и <tex> s_{i+1} </tex> простые, то из доказанной [[Декомпозиция Линдона#lemma | леммы]] следует, что эти слова можно сконкатенировать и получить разбиение строки <tex> s </tex> на меньшее число слов. Получили противоречие.
Таким образом доказали даже более сильное утверждение: <tex>s = s_1 s_2 ... \ldots s_k</tex>, <tex> k </tex> {{---}} минимально <tex>\Leftrightarrow</tex> нет <tex>s_i < s_{i+1}</tex>
'''2. Единственность.'''
Пусть существует несколько разбиений <tex>s = s_1s_2...\ldots s_k = s_1's_2'...\ldots s_k'</tex>,
удовлетворяющих условию теоремы.
Сравним длины первых двух слов <tex>s_1</tex> и <tex>s_1'</tex>, если <tex>|s_1| = |s_1'|</tex>, сравним вторые и так далее.
Покажем, что такого не может быть:
1) Пусть <tex>|s_i| > |s_i'|</tex>, тогда <tex>s_i = s_i's_{i+1}'...\ldots t</tex>, где <tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>, <tex>i < j</tex>. Тогда получаем:
* <tex>s_i < t</tex> (<tex>s_i</tex> {{---}} простая cтрока и по определению меньше своего суффикса)
* <tex>t < s_{j+1}'</tex> (<tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>)
===Корректность===
Покажем, что алгоритм получает нужное разложение. То есть все <tex>s_i</tex> {{---}} простые, и <tex>s_1 \geqslant s_2 \geqslant ... \ldots \geqslant s_k</tex> лексикографически.
При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Мы сравниваем символы в <tex> w </tex> и <tex> w' </tex> на одинаковых позициях, а <tex> w' </tex> {{---}} префикс <tex> w </tex>, поэтому инвариант сохраняется.
Покажем, что <tex>\forall\tau: 1\leqslant\tau\log{n}</tex> существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса <tex>O(\tau)</tex> и временем препроцессинга <tex>O(n\log{n/\tau})</tex> для запросов на нахождение минимального суффикса.
* по индексам <tex>i</tex> и <tex>j</tex> вычислить максимальный и минимальный суффикс в <tex>Suf[i,j]</tex>
Более того, такой <b>улучшенный суффиксный массив</b> может отвечать на запрос "по данным <tex>x,y</tex> {{---}} подстрокам <tex>T</tex> вычислить максимальное чило <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является префиксом <tex>y</tex>" за константное время. Действительно, стоит заметить, что если <tex>x</tex> {{---}} префикс <tex>y = T[i..\ldots j]</tex>, то <tex>\alpha |x| \leqslant lcp(T[i..\ldots j],T[i+|x|..\ldots j] < (\alpha+1)|x|)</tex>
Запросы к перевёрнутому улучшенному суфмассиву <tex>T^{R}</tex>также имеют смысл. С его помощью мы можем для пары <tex>x,y</tex> подстрок <tex>T</tex> найти их наибольший общий суффикс <tex>lcs(x,y)</tex> и наибольшее число <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является суффиксом <tex>y</tex>.
Возьмём строку <tex>T</tex> длины <tex>n</tex>. Для каждой позиции <tex>j</tex> мы выберем <tex>O(logN\log{N})</tex> подстрок <tex>T[k..\ldots j]</tex>, которые мы назовём каноническими. Определим как <tex>S^{l}_{j}</tex> <tex>l</tex>-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции <tex>j</tex>. Для пары целых чисел <tex>1\leqslant i<j\leqslant n</tex> мы определим как <tex>\alpha(i,j)</tex> наибольшее <tex>l</tex>, такое, что <tex>S^{l}_{j}</tex> {{---}} суффикс <tex>T[i..\ldots j]</tex>.
Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
*<tex>S^{1}_{j} = T[j..\ldots j]</tex> и для некоторого <tex>l=O(logN\log{N})</tex> выполняется <tex>S^{l}_{j} = T[1..\ldots j]</tex>
*<tex>\forall l:|S^{l+1}_{j}|\leqslant 2|S^{l}_{j}|</tex>
*<tex>\alpha(i,j)</tex> и <tex>|S^{l}_{j}|</tex> можно вычислить за константное время для данных <tex>(i,j)</tex> и <tex>(i,l)</tex> соответственно
Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем <tex>|S^{l}_{j}| = \min(2^{l-1}, j)</tex>
{{Лемма
|id=lemma
|author=0
|statement= Пусть <tex>T[\mu \ldots j]</tex> - искомый лексикографически наименьший суффикс. Если у <tex>T[m \ldots j]</tex> нет непустых бордеров, то <tex>T[\mu \ldots j] = T[m \ldots j]</tex>. Иначе <tex>T[\mu \ldots j]</tex> {{---}} кратчайший непустой бордер <tex>T[m \ldots j]</tex>.<ref name="ref1">[http://starikovskaya.files.wordpress.com/2013/07/on-minimal-and-maximal-suffixes-of-a-substring.pdf On Minimal and Maximal Suffixes of a Substring]</ref>
|proof= Покажем, что <tex>T[\mu \ldots j]</tex> является одновременно префиксом и суффиксом <tex>T[m \ldots j]</tex>. Если <tex>T[m \ldots j]=T[\mu \ldots j]</tex>, то лемма доказана, иначе <tex>T[\mu \ldots j]\prec T[m \ldots j]</tex>. По определению лексикографического порядка, либо <tex>(1)</tex> <tex>T[\mu \ldots j]</tex> является префиксом <tex>T[m \ldots j]</tex>, либо <tex>(2)</tex> существует <tex>\displaystyle \ell<\min(|T[\mu \ldots j]|,\ |T[m \ldots j]|)</tex> такой, что <tex>T[\mu \ldots \mu+ \ell]=T[m \ldots m+\ell]</tex>, и <tex>T[\mu+\ell+1]<T[m+\ell+1]</tex>.
В случае <tex>(1)</tex> выполняется <tex> m<\mu</tex> и таким образом <tex>T[\mu \ldots j]</tex> также является суффиксом <tex>T[m \ldots j]</tex>. Покажем, что второй случай никогда не выполняется. Действительно, <tex>T[\mu \ldots ]\prec T[m \ldots ]</tex>, но в <tex>Suf [i,\ j]</tex> <tex>T[m \ldots ]</tex> является лексикографически наименьшим суффиксом.
Следовательно, <tex>T[\mu \ldots j]</tex> является одновременно префиксом и суффиксом <tex>T[m \ldots j]</tex>. Если <tex>T[m \ldots j]</tex> не имеет непустых бордеров, то <tex>\mu=m</tex>. Иначе, <tex>T[\mu \ldots j]</tex> является бордером <tex>T[m \ldots j]</tex>. Предположим, <tex>T[\mu \ldots j]</tex> - не наименьший непустой бордер <tex>T[m \ldots j]</tex>, тогда существует более короткий бордер <tex>\beta</tex>. По определению, <tex>\beta</tex> {{---}} префикс <tex>T[m \ldots j]</tex>, следовательно он также является префиксом <tex>T[\mu \ldots j]</tex>. Следовательно, <tex>\beta\prec T[\mu \ldots j]</tex>, что приводит нас к противоречию.
}}
{{Лемма
|id=lemma2
|author=1
|statement= Минимальный суффикс <tex>T[i..\ldots j]</tex> равен либо
<tex>(a)\ T[p..\ldots j]</tex>, где <tex>p</tex> {{---}} начальная позиция минимального суффикса в <tex>Suf[i,j]</tex>, либо
<tex>(b)</tex> минимальному суффиксу <tex>|S^{\alpha(i,j)}_{j}|</tex>.
Более того, <tex>p</tex> может быть найдено за константное время с использованием улучшенного суффиксного массива строки <tex>T</tex>.
|proof= По Лемме 1 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 5] лемме 0 минимальный суффикс равен либо <tex>T[p..\ldots j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..\ldots j]|\leqslant\frac{1}{2}|T[i..\ldots j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..\ldots j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..\ldots j]</tex> является минимальным суффиксом <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется случай <tex>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.
}}
Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого <tex>j=1,\ \ldots,\ n</tex> содержать битовый вектор <tex>B_{j}</tex> длиной <tex>\alpha(1,\ j)</tex>. Положим <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда минимальный суффикс <tex>S_{j}^{\ell}</tex> длиннее, чем <tex>|S_{j}^{\ell-1}|</tex>. Для <tex>\ell=1</tex> мы всегда считаем <tex>B_{j}[1]=1</tex>, поскольку <tex>S_{j}^{1}</tex> является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого <tex>j</tex> равна <tex>\mathcal{O}(\log n)</tex> , поэтому каждый <tex>B_{j}</tex> вмещается в константное количество машинных слов и структура данных занимает <tex>\mathcal{O}(n)</tex> памяти.
===Алгоритм запроса===
Предположим, что мы ищем минимальный суффикс <tex>T[i..\ldots j]</tex> c <tex>\alpha(i,\ j)=\ell</tex>. Наш подход основан на Лемме лемме 1. Если выполняется случай <tex>(a)</tex>, лемма позволяет нам вычислить ответ за <tex>\mathcal{O}(1)</tex>. В общем случае, мы найдём минимальный суффикс <tex>S_{j}^{\ell}</tex>, сравним его с <tex>T[p..\ldots j]</tex> и вернём меньший из них.
Мы используем Лемму лемму 1 и битовый вектор <tex>B_{j}</tex> чтобы посчитать минимальный суффикс <tex>S_{j}^{\ell}</tex>. Назовём <tex>\ell'</tex> наибольший индекс, не превышающий <tex>\ell</tex>, такой, что <tex>B_{j}[\ell']=1</tex>. Заметим, что такой индекс всегда существует (поскольку<tex> B_{j}[1]=1</tex>) и может быть найден за константное время с использованием битовых операций. Для любого индекса <tex>\ell''\in\{\ell'+1,\ \ldots,\ \ell\}</tex> мы имеем <tex>B_{j}[\ell'']=0</tex>, т.е., случай <tex>(b)</tex> Леммы леммы 1 выполняется для <tex>S_{j}^{\ell''}</tex>. Тогда, по индукции, минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>. С другой стороны, <tex>B_{j}[\ell']=1</tex>, поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс <tex>S_{j}^{\ell}</tex> за константное время.
===Построение искомой структуры данных===
Простой алгоритм построения с временем работы <tex>\mathcal{O}(n\log n)</tex> также основывается на Лемме лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти <tex>B_{j}</tex> за <tex>\mathcal{O}(\log n)</tex>. Мы ищем минимальный суффикс <tex>S_{j}^{\ell}</tex> для последовательных значений <tex>\ell</tex>. Как только мы получили результат <tex>\ell-1</tex>, случай <tex>(a)</tex> Леммы леммы 1 даёт нам второго кандидата на минимальный суффикс <tex>S_{j}^{\ell}</tex>, и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем <tex>B_{j}[\ell]=1</tex> если меньший кандидат не содержится в <tex>S_{j}^{\ell-1}</tex>. Стало быть, мы получили следующий результат:
{{Теорема
Вышеописанная конструкция проста и работает для любого выбора канонических подстрок, но, к сожалению, она не может быть использована для достижения компромисса между временем запроса и временем построения. Далее мы предложим особый способ выбора канонических подстрок и опишем альтернативный метод построения. Этот способ основывается на предположении, что по данной строке длины <tex>k</tex> мы можем найти минимальный суффикс для всех её префиксов за <tex>\mathcal{O}(k)</tex>. Следовательно, нам удобно иметь много <tex>S_{j}^{\ell}</tex>, которые являются префиксами друг друга. Тогда, естественным будет выбрать <tex>|S_{j}^{\ell}|=2^{\ell-1}+(j\ mod\ 2^{\ell-1})</tex> , поскольку все подстроки <tex>S_{\alpha 2^{l-1}}^{\ell},\ S_{\alpha 2^{l-1}+1}^{\ell},\ \ldots,\ S_{(\alpha+1)2^{l-1}-1}^{\ell}</tex> являются префиксами <tex>S_{(\alpha+1)2^{l-1}-1}^{\ell}</tex>. К сожалению, подстроки, выбранные таким способом, не удовлетворяют условию <tex>|S_{j}^{\ell}|\leqslant 2|S_{j}^{\ell-1}|</tex>, и, посему, нам необходимо немного изменить его.
Для <tex>\ell=1</tex> мы определим <tex>S_{j}^{1}=T[j..\ldots j]</tex>. Для <tex>\ell>1</tex> установим <tex>m=\lfloor\ell/2\rfloor-1</tex> и определим <tex>S_{j}^{\ell}</tex> таким образом:
<tex>
|S_{j}^{\ell}|=
\end{cases}</tex>
Заметим, что если <tex>2 \cdot 2^{m}\leqslant j<3\cdot 2^{m}</tex>, то <tex>T[1..\ldots j]=S_{j}^{2m+2}</tex>, в то время как, если <tex>3 \cdot 2^{m}\leqslant j<4\cdot 2^{m}</tex>, то <tex>T[1..\ldots j]=S_{j}^{2m+3}</tex>. Очевидно, что количество таких подстрок, заканчивающихся в <tex>j</tex> получается <tex>\mathcal{O}(\log n)</tex>. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.
{{Утверждение
|author=4
|statement= Для <tex>1\leqslant i<j\leqslant n</tex>, величина <tex>\alpha(i,\ j)</tex> может быть посчитана за константное время.
|proof= Положим <tex> m=\lfloor\log|T[i..\ldots j]|\rfloor</tex>. Заметим, что
<tex>|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})<2^{m}\leqslant|T[i..\ldots j]|</tex>
<tex>|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geqslant 2^{m+1}>|T[i..\ldots j]|</tex>.
Таким образом, <tex>\alpha(i,\ j)\in\{2m-1,2m,\ 2m+1\}</tex>, и мы можем за константное время проверить, какое из этих трёх значений корректно.
}}
После построения улучшенного суфмассива, мы установили все биты<tex>B_{j}[1]</tex> в 1. После этого, для каждого <tex>\ell>1</tex> мы посчитали минимальные суффиксы подстрок <tex>S_{j}^{\ell}</tex>, как указано далее. Зафиксируем <tex>\ell>1</tex> и разобьём <tex>T</tex> на куски размером <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) . Теперь каждый <tex>S_{j}^{\ell}</tex> является префиксом конкатенации максимум 4х таких кусков. ВспомнимИзвестно, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля (Алгоритм 3.1 in <ref name="ref2">[http://wwwge.sciencedirect.comtt/api/1/sciencefiles/article5uKJjWQ/pii0/0196677483900172 6blob?download Factorizing words over an ordered alphabet])</ref>. Разделим <tex>T</tex> на куски длиной <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы <tex>S_{j}^{\ell}</tex> для всех <tex>1\leqslant j\leqslant n</tex>, за время <tex>\mathcal{O}(n)</tex>. Значение <tex>B_{j}[\ell]</tex> определено с помощью сравнения длины вычисленного минимального суффикса <tex>S_{j}^{\ell}</tex> с <tex>|S_{j}^{\ell-1}|</tex>. У нас <tex>\mathcal{O}(\log n)</tex> фаз алгоритма, что даёт нам время <tex>\mathcal{O}(n\log n)</tex> и <tex>\mathcal{O}(n)</tex> требуемой памяти.
===Компромисс===
Чтобы получить структуру данных, со временем построения <tex>\mathcal{O}(n\log n/\tau)</tex> и временем запроса <tex>\mathcal{O}(\tau)</tex>, мы немного по-другому определим битовые вектора. Положим <tex>B_{j}</tex> размером <tex>\lfloor\alpha(1,\ j)/\tau\rfloor</tex>, притом <tex>B_{j}[k]=1</tex> тогда и только тогда, когда <tex>k=1</tex> или минимальный суффикс <tex>S_{j}^{\tau k}</tex> длиннее, чем <tex>|S_{j}^{\tau(k-1)}|</tex>. В этом случае, нам необходимо только <tex>\mathcal{O}(\log n/\tau)</tex> фаз в алгоритме построения, поэтому он займёт <tex>\mathcal{O}(n\log n/\tau)</tex> времени.
Как и ранее, предположим, что мы ищем минимальный суффикс <tex>T[i..\ldots j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом {{---}} найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leqslant\ell</tex>, такой, что минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>, но длиннее, чем <tex>|S_{j}^{\ell'-1}|</tex>. Если <tex>\ell=\tau k</tex> для целого <tex>k</tex>, мы можем найти наибольший <tex>k'\leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что <tex>\tau k\leqslant\ell</tex>, и будем знать, что мы должны рассмотреть <tex>\ell'\in(\tau k,\ \ell]</tex> и <tex> \ell'\in(\tau(k'-1),\ \tau k']</tex>, где <tex>k'</tex> определён, как в предыдущем случае. В результате, мы имеем <tex>\mathcal{O}(\tau)</tex> возможных значений <tex>\ell'</tex>, и нам изестноизвестно, что искомый суффикс может быть найден, используя случай <tex>(a)</tex> Леммы леммы 1 для <tex>S_{j}^{\ell'}</tex> для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за <tex>\mathcal{O}(\tau)</tex>.
'''Из вышеописанного следует теорема:'''
{{Теорема
|author=5
|statement=
Для любого <tex>1\leqslant\tau\leqslant\log n</tex>, строка <tex>T</tex> длиной <tex>n</tex> может храниться в структуре данных, занимающей <tex>\mathcal{O}(n)</tex> памяти, позволяющей вычислять минимальный суффикс любой из подстрок <tex>T</tex> за время <tex>\mathcal{O}(\tau)</tex>. Такая структура данных может быть построена за <tex>\mathcal{O}(n\log {n/\tau})</tex>.
}}
|author=7
|id=lemma
|statement= Рассмотрим подстроку <tex>T[i..\ldots j]</tex>. Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> времени можно найти такой индекс <tex>p\ (i\leqslant p\leqslant j)</tex>, что максимальный суффикс <tex>T[\mu..\ldots j]</tex> строки <tex>T[i..\ldots j]</tex> равен либо
<tex>(a) T[p..\ldots j]</tex>, либо
<tex>(b)</tex> максимальному суффиксу строки <tex>S_{j}^{\alpha(i,j)}</tex>
|proof=
}}
Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора <tex>B_{j},\ j\in[1,\ n]</tex>, с <tex>B_{j}[\ell]=1</tex>, если <tex>\ell=1</tex> или максимальный суффикс строки <tex>S_{j}^{\ell}</tex> длиннее <tex>|S_{j}^{\ell-1}|</tex>. Алгоритм запроса, описанный в части 4.1[[#Алгоритм_запроса|здесь]], очевидно, может быть адаптирован к нашей задаче, только вместо леммы 1 мы будем использовать лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:
|statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных с <tex>\mathcal{O}(n)</tex> памяти, которая позволяет вычислять максимальный суффикс любой подстроки строки <tex>T</tex> за время <tex>\mathcal{O}(1)</tex>.
|proof=
Алгоритмы построения за <tex>\mathcal{O}(n\log n)</tex> и компромисс между временем запросов и временем построения, описанные в пунктах 4.2 [[#Построение искомой структуры данных|здесь]] и 4.3[[#Компромисс|здесь]] соответственно, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения <tex>\mathcal{O}(n)</tex>, как будет показано в пункте 5.2ниже.
}}
Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию <tex>p\in[i,\ j]</tex>.
Заметим, что если максимальный суффикс <tex>T[\mu..\ldots j]</tex> of <tex>T[i..\ldots j]</tex> короче, чем <tex>S_{j}^{\alpha(i,j)}</tex> (случай (b) леммы 7), алгоритм может вернуть любое <tex>p\in[i,\ j]</tex>. Далее мы предполагаем, что <tex>T[\mu..\ldots j]</tex> длиннее, чем <tex>S_{j}^{\alpha(i,\ j)}</tex> и показываем, что при этом предположении алгоритм вернёт <tex> p=\mu</tex>. Из нашего предположения свойств канонических подстрок следует, что <tex>\mu\in[i,\ r]</tex>, where <tex>r=j-|S_{j}^{\alpha(i,\ j)}|</tex>, и что длины суффиксов подстроки <tex>T[i..\ldots j]</tex>, начинающихся с позиций в промежутке <tex>[i,\ r]</tex>, отличаются не более чем в два раза. Мы начнем со вспомогательной леммы, которая обозначалась как лемма 2 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6]
Мы начнем со вспомогательной леммы, которая обозначалась как лемма 2 в <ref name="ref1"/>
{{Лемма
|id=lemma
|author=9
|statement= Пусть <tex>P_{1}=T[p_{1}..\ldots j]</tex> {{---}} префикс строки <tex>T[\mu..\ldots j]</tex> и пусть <tex>P_{2}=T[p_{2}..\ldots j]</tex>, где <tex>T[p_{2}..\ldots j]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Если <tex>P_{1}</tex> не является префиксом <tex>P_{2}</tex>, тогда <tex>\mu=p_{1}</tex>. Иначе, <tex>P_{2}</tex> также является префиксом строки <tex>T[\mu..\ldots j]</tex>.
|proof= Пусть <tex>T[p_{1}..\ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..\ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1}..\ldots j]</tex> является префиксом строки <tex>T[\mu..\ldots j]</tex>. Предположим, что <tex>P_{1}</tex> {{---}} префикс <tex>P_{2}</tex> (иначе <tex>p_{1}=\mu\</tex> по лемме 9). Длины <tex>P_{1}</tex> и <tex>P_{2}</tex> различаются не более чем в два раза, поэтому <tex>2|P_{1}|\geqslant|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют леммы 4 и 5 из [http:<ref name="ref1" //link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6]>, но здесь мы приводим доказательства вследствие другого обозначения.
}}
|id=lemma
|author=10
|statement= Подстрока <tex>\rho=T[p_{2}..\ldots p_{1}-1]</tex> {{---}} минимальный период строки <tex>P_{2}</tex>, т.е. <tex>\rho</tex> {{---}} кратчайшая строка, такая, что для какого-то <tex>s\geqslant 1</tex> выполняется <tex>P_{2}=\rho^{s}\rho'</tex>.|proof= Поскольку <tex>P_{1}</tex> {{---}} бордер <tex>P_{2},\ \rho=T[p_{2}..\ldots p_{1}-1]</tex> {{---}} период <tex>P_{2}</tex>. Остается лишь доказать, что невозможно найти более короткий период. Таким образом, рассмотрим(consider) кратчайший период <tex>\gamma</tex>, и предположим, что <tex>|\gamma|<|\rho|</tex>. Тогда <tex>|\gamma|+|\rho|\leqslant 2|\rho|\leqslant|T[p_{2}..\ldots j]|</tex>, и по лемме о периодичности подстрока <tex>P_{2}</tex> имеет другой период <tex>\mathrm{g}\mathrm{c}\mathrm{d}(|\gamma|,\ |\rho|)</tex> . Так как <tex>\gamma</tex> {{---}} кратчайший период, то <tex>|\rho|</tex> должно быть степенью <tex>|\gamma|</tex>, т.е. <tex>\rho=\gamma^{k}</tex> для какого-то <tex>k\geqslant 2</tex>.
Предположим, что <tex>T[p_{1}..\ldots ]\prec\gamma T[p_{1}..\ldots ]</tex> '''(лексикографически меньше)'''. Тогда приписывание к обеим частям последнего неравенства степеней <tex>\gamma</tex> даёт <tex>\gamma^{\ell-1}T[p_{1}..\ldots ]\prec\gamma^{\ell}T[p_{1}..\ldots ]</tex> для любого <tex>1\leqslant\ell\leqslant k</tex>, таким образом из транзитивности <tex>\prec</tex> получаем <tex>T[p_{1}..\ldots ]\prec\gamma^{k}T[p_{1}..\ldots ]=T[p_{2}..\ldots ]</tex>, что противоречит максимальности <tex>T[p_{1}..\ldots ]</tex> in <tex>Suf[i,\ r]</tex>. Таким образом, <tex>T[p_{1}..\ldots ]\succ\gamma T[p_{1}..\ldots ]</tex>, и следовательно <tex>\gamma^{k-1}T[p_{1}..\ldots ]\succ\gamma^{k}T[p_{1}..\ldots ]</tex>. Но <tex>\gamma^{k-1}T[p_{1}..\ldots ]=T[p_{2}+|\gamma|..\ldots ]</tex> и <tex>\gamma^{k}T[p_{1}..\ldots ]=T[p_{2}..\ldots ]</tex>, поэтому <tex>T[p_{2}+|\gamma|..\ldots ]</tex> больше, чем <tex>T[p_{2}..\ldots ]</tex> и принадлежит <tex>Suf [i,\ p_{1}-1]</tex>, противоречие. Заметим, что на самом деле <tex>s\geqslant 2</tex>, потому что <tex>2|P_{1}|\geqslant|P_{2}|=|P_{1}|+|\rho|</tex>, поэтому <tex>|P_{1}|\geqslant|\rho|.\ </tex>
}}
|id=lemma
|author=11
|statement= Положим, <tex>P_{2}=\rho P_{1}=\rho^{s}\rho'</tex>. Тогда максимальный суффикс <tex>T[\mu..\ldots j]</tex> {{---}} длиннейший суффикс строки <tex>T[i..\ldots j]</tex> равен <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>. (См. рисунок 1)|proof= Очевидно, что <tex>P_{2}</tex> является бордером <tex>T[\mu..\ldots j]</tex>. Из <tex>P_{2}=\rho P_{1}</tex> и <tex>|T[\mu..\ldots j]|\leqslant 2|P_{1}|</tex> имеем <tex>|T[\mu..\ldots j]|+|\rho|\leqslant 2|P_{1}|+\rho\leqslant 2|P_{2}|</tex>. Следовательно вхождения <tex>P_{2}</tex> в качестве префикса и в качестве суффикса строки <tex>T[\mu..\ldots j]</tex> перекрывают друг друга как минимум в <tex>|\rho|</tex> позициях. Т.к. <tex>|\rho|</tex> {{---}} период <tex>P_{2}</tex>, отсюда следует, что <tex>|\rho|</tex> также является периодом <tex>T[\mu..\ldots j]</tex>. Таким образом, <tex>T[\mu..\ldots j]=\rho''\rho^{r}\rho'</tex>, где <tex>r</tex> {{---}} целое число и <tex>\rho''</tex> {{---}} суффикс <tex>\rho</tex>. Более того, <tex>\rho^{2}</tex> {{---}} это префикс <tex>T[\mu..\ldots j]</tex>, поскольку является префиксом <tex>P_{2}</tex>, который в свою очередь является префиксом <tex>T[\mu..\ldots j]</tex>. Теперь <tex>\rho''\neq\xi j</tex> будет означать нетривиальное вхождение <tex>\rho</tex> в <tex>\rho^{2}</tex>, которое противоречит примитивности <tex>\rho</tex>, смотри <ref name="ref4">[http://www.google.ru/books?hl=en&lr=&id=PuOOY_DR55UC&oi=fnd&pg=PR7&dq=M.+Crochemore,+C.+Hancart,+and+T.+Lecroq.+Algorithms+on+Strings.+Cambridge+University+Press,+2007&ots=oe_VacDwgA&sig=PKoDRn6K6nZsWfajL0-0jkSlAf8&redir_esc=y#v=onepage&q&f=false 7M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007]</ref>.
[[Файл:image001.png|Рис. 1. Схематичная иллюстрация к лемме 11.|800px]]
Таким образом, <tex>T[\mu..\ldots j]=\rho^{r}\rho'</tex>. Если <tex>t>r</tex>, тогда <tex>\rho^{t}\rho'\succ\rho^{r}\rho'</tex>, поэтому <tex>T[\mu..\ldots j]</tex> {{---}} длиннейший суффикс строки <tex>T[i..\ldots j]</tex>, равный <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>.
}}
'''Доказательство леммы 7'''
<tex>\triangleright</tex>
Пусть <tex>T[p_{1}..\ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..\ldots ]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Сначала вычислим <tex>p_{1}</tex> и <tex>p_{2}</tex> за <tex>\mathcal{O}(1)</tex>, используя улучшенный суффиксный массив. Затем проверим, что <tex>T[p_{1}..\ldots j]</tex> является префиксом <tex>T[p_{2}..\ldots j]</tex>. Если это неверно, то мы возвращаем <tex>p=p_{1}</tex>. Иначе, мы вычисляем максимальное целое число <tex>r</tex>, такое, что <tex>\rho^{r}</tex> (для <tex>\rho=T[p_{2}..\ldots p_{1}-1])</tex>) {{---}} суффикс <tex>T[i..\ldots p_{1}-1]</tex>, используя метод из алгоритма поиска минимального суффикса, и возвращаем <tex>p=p_{1}-r|\rho|</tex>. Из вышеописанных лемм следует, что если <tex>T[\mu..\ldots j]</tex> длиннее <tex>S_{j}^{\alpha(i,\ j)}</tex>, тогда <tex> p=\mu</tex>.
<tex>\triangleleft</tex>
===Построение искомой структуры данных===
Наш алгоритм основывается на следующем понятии. Для <tex>1\leqslant p\leqslant j\leqslant n</tex> мы говорим, что позиция <tex>p</tex> <tex>j</tex>-активна, если не существует такой позиции <tex>p'\in\{p+1,\ \ldots,\ j\}</tex>, что <tex>T[p'..\ldots j]\succ T[p..\ldots j]</tex>. Другими словами, <tex>p</tex> {{---}} <tex>j</tex>-активна тогда и только тогда, когда <tex>T[p..\ldots j]</tex> {{---}} максимальный суффикс самого себя. Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки <tex>T[i..\ldots j]</tex> {{---}} это минимальная <tex>j</tex>-активная позиция в промежутке <tex>[i,\ j]</tex>. Следовательно, при <tex>\ell>1</tex> мы имеем <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда существует как минимум одна <tex>j</tex>-активная позиция в диапазоне <tex>R_{j}^{\ell}=[j-|S_{j}^{\ell}|+1,\ j-|S_{j}^{\ell-1}|]</tex>. Положим <tex>R_{j}^{1}=[j,\ j]</tex>, тогда это равенство также сохраняется для <tex>\ell=1</tex> (поскольку <tex>j</tex> всегда <tex>j</tex>-активна)
'''''Пример (12):''''' Если <tex>T[1..\ldots 8]=dcccabab</tex>, то 8-активными позициями будут <tex>1,\ 2,\ 3,\ 4,\ 6,\ 8.</tex>
Алгоритм построения перебирает <tex>j</tex> от <tex>1</tex> до <tex>n</tex>, сохраняя список активных позиций и вычисляя битовые вектора <tex>B_{j}</tex>. Мы также сохраняем диапазоны <tex>R_{j}^{\ell}</tex> для выбора канонических подстрок, описанных в пункте 4.2[[#Построение искомой структуры данных|здесь]], которые образуют разбиение <tex>[</tex>1, <tex>\ j]</tex>. Два следующих результата описывают изменения списка <tex>j</tex>-активных позиций и диапазонов <tex>R_{j}^{\ell}</tex>, когда мы увеличиваем <tex>j</tex>.
{{Лемма
|statement= Если список всех <tex>(j-1)</tex>-активных позиций состоит из <tex>p_{1}<p_{2}<</tex> . . . <tex><p_{k}</tex>, то список <tex>j</tex>-активных позиций может быть создан путём добавления <tex>j</tex>, и повторения следующей процедуры: если <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> {{---}} два соседа в текущем списке и <tex>T[j]\neq T[j+p_{\ell}-p_{\ell+1}]</tex>, удаляем <tex>p_{\ell}</tex> или <tex>p_{\ell+1}</tex> из списка, зависимо от того, что <tex>T[j]>T[j+p_{\ell}-p_{\ell+1}]</tex> или <tex>T[j]<T[j+p_{\ell}-p_{\ell+1}]</tex>, соответственно.
|proof= Сначала мы докажем, что если позиция <tex>1\leqslant p\leqslant j-1</tex> не является <tex>(j-1)</tex>-активной, то она также не является и <tex>j</tex>-активной. Действительно, если <tex>p</tex> не <tex>(j-1)</tex>-активна, тогда по определению существует позиция <tex>p<p'\leqslant j-1</tex>, такая, что <tex>T[p..\ldots j-1]\prec T[p'..\ldots j-1]</tex>. Следовательно, <tex>T[p..\ldots j]=T[p..\ldots j-1]T[j]\prec T[p'..\ldots j-1]T[j]=T[p'..\ldots j]</tex> и <tex>p</tex> не является <tex>j</tex>-активной. Отсюда, единственными кандидатами на <tex>j</tex>-активные позиции остаются <tex>(j-1)</tex>-активные позиции и <tex>j</tex>.
Далее, заметим, что если <tex>1\leqslant p\leqslant j-1</tex> {{---}} <tex>\mathrm{a}(j-1)</tex>-активная позиция и <tex>T[p'..\ldots j-1]</tex> {{---}} префикс <tex>T[p..\ldots j-1]</tex>, то <tex>p'</tex> тоже является <tex>(j-1)</tex>-активной. Если это не так, тогда существует позиция <tex>p'',\ p'<p''<j-1</tex>, такая, что <tex>T[p'..\ldots j-1]\prec T[p''..\ldots j-1]</tex>, и из этого следует, что <tex>T[p..\ldots j-1]=T[p'..\ldots j-1]T[j+p-p'..\ldots j-1]\prec T[p''..\ldots j-1]</tex>, противоречие. <tex>\mathrm{A}(j-1)</tex>-активная позиция <tex>p</tex> не является <tex>j</tex>-активной только если (1) <tex>T[j]\geqslant T[p]</tex> или (2) существует <tex>p<p'\leqslant j-1</tex> такая, что <tex>T[p'..\ldots j-1]</tex> {{---}} префикс <tex>T[p..\ldots j-1]</tex>, т.е. <tex>p'</tex> {{---}} <tex>(j-1)</tex>-активна и <tex>T[p'..\ldots j]\succ T[p..\ldots j]</tex> или, другими словами, <tex>T[j]>T[j+p-p']</tex>. Оба этих случая выявляются процедурой удаления.
}}
'''''Пример (14):''''' Если <tex>T[1..\ldots 9]=dcccababb</tex>, то 8-активными позициями будут: <tex>1,\ 2,\ 3,\ 4,\ 6,\ 8,</tex> и 9-активными позициями будут: <tex>1,\ 2,\ 3,\ 4,\ 8,\ 9,</tex> т.е. мы добавляем <tex>9</tex> в наш список 8-активных позиций, а затем удаляем <tex>6</tex>.
{{Утверждение
Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[</tex>1, <tex>\ j]</tex> на диапазоны <tex>R_{j}^{\ell}</tex>. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что <tex>B_{j}[\ell]=1</tex> только когда <tex>l</tex>-й счетчик не равен нулю. Чтобы эффективно обновить список <tex>(j-1)</tex>-активных позиций и получить список <tex>j</tex>-активных позиций, мы также храним для каждого <tex>j'</tex> список указателей на пары соседних позиций, таких, что одна из них должна быть удалена, когда мы достигнем <tex>j=j'</tex>. Всякий раз когда появляется новая пара соседних позиций <tex>p_{z},\ p_{z+1}</tex>, мы считаем <tex>L=</tex> <tex>lcp</tex> <tex>(T[p_{z}..\ldots],\ T[p_{z+1}..\ldots])</tex> и с этого момента наименьший <tex>j'=p_{z}+L</tex>, когда одна из них должна быть удалена из списка, и вставляем указатель на пару <tex>p_{z},\ p_{z+1}</tex> в <tex>j'</tex>-й список. Когда мы действительно достигнем <tex>j=j'</tex>, мы проследуем по указателю и проверим, что <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем.
Из леммы 13 следует, что два возможных обновления списка при переходе от <tex>j-1</tex> к <tex>j</tex> добавляют <tex>j</tex> или удаляют какую-то позицию из списка. Это гарантирует, что процесс удаления из леммы 13 и процесс, который мы описали, эквивалентны.
Предположим, что мы уже знаем список <tex>(j-1)</tex>-активных позиций, битовый вектор <tex>B_{j-1}</tex>, и число <tex>(j-1)</tex>-активных позиций в каждом диапазоне <tex>R_{j-1}^{\ell}</tex>. Сначала мы обновим список <tex>(j-1)</tex>-активных позиций. Когда позиция удалена из списка, мы находим диапазон, к которому она принадлежит и уменьшаем его счетчик внутренних позиций. Если счетчик становится нулевым, мы очищаем соответствующий бит битового вектора. Далее мы начинаем обновлять разбиение: сначала мы добавляем новый диапазон <tex>[j,\ j]</tex> к разбиению <tex>[1..\ldots j-1]</tex> и инициализируем счетчик активных позиций единицей. Затем, мы обновлям первые <tex>2k+4</tex> диапазонов (<tex>k</tex> {{---}} максимальная степень <tex>2</tex>, которой кратно <tex>j</tex>), используя теорему 15, а также счетчики и битовый вектор. Этот процесс займет <tex>\mathcal{O}(k)</tex> времени, что амортизированно составляет
<tex>\displaystyle \mathcal{O}(\sum_{k=1}^{\infty}\frac{k}{2^{k}})=\mathcal{O}(1)</tex> при всех значениях <tex>j</tex>.
}}
==См. также==
* [[Алгоритм Крочемора]]
* [[Суффиксный массив]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
==Примечания==
<references/>
==Источники информации==
*[[wikipedia:Lyndon word | Wikipedia {{---}} Lyndon word ]]
*[http://books.google.ru/books?id=Q5K3vREGVhAC&printsec=frontcover#v=onepage&q&f=false Algebras, Rings, and Modules: Lie Algebras and Hopf Algebras", Michiel Hazewinkel, Nadezhda Mikhaĭlovna Gubareni, Vladimir V. Kirichenko, страница 242]
*[http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&ved=0CF0QFjAE&url=http%3A%2F%2Fmimuw.edu.pl%2F~kociumaka%2Ffiles%2Fcpm2014a_draft.pdf&ei=__CIU_7gLYap4gTw7YDACA&usg=AFQjCNG-fcqnjok7hpyiO8niGTFTSOgBJQ&sig2=Ku2k8vAz4QJHolkr_BOLyQ&bvm=bv.67720277,d.bGE&cad=rjt Computing minimal and maximal suffixes of a substring revisited]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Основные определения. Простые комбинаторные свойства слов]]
