8
правок
Изменения
Нет описания правки
<tex>\triangleleft</tex>
===Построение===
Наш алгоритм основывается на следующем понятии. Для <tex>1\leq p\leq j\leq n</tex> мы говорим, что позиция <tex>p</tex> <tex>j</tex>-активна, если не существует такой позиции <tex>p'\in\{p+1,\ \ldots,\ j\}</tex>, что <tex>T[p'..j]\succ T[p..j]</tex>. Другими словами, <tex>p</tex> — <tex>j</tex>-активна тогда и только тогда, когда <tex>T[p..j]</tex> — максимальный суффикс самого себя.
Максимальный суффикс любой строки является своим собственным максимальным суффиксом, поэтому из определения следует, что стартовая позиция максимального суффикса строки <tex>T[i..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>-активна)
'''''Пример:''''' Если <tex>T[1..8]=dcccabab</tex>, то 8-активными позициями будут 1, 2, 3, 4, 6, 8.
Алгоритм построения перебирает <tex>j</tex> от 1 до <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>.
{{Лемма
|id=lemma
|author=13
|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\leq p\leq j-1</tex> не является <tex>(j-1)</tex>-активной, то она также не является и <tex>j</tex>-активной. Действительно, если <tex>p</tex> не <tex>(j-1)</tex>-активна, тогда по определению существует позиция <tex>p<p'\leq j-1</tex>, такая, что <tex>T[p..j-1]\prec T[p'..j-1]</tex>. Следовательно, <tex>T[p..j]=T[p..j-1]T[j]\prec T[p'..j-1]T[j]=T[p'..j]</tex> и <tex>p</tex> не является <tex>j</tex>-активной. Отсюда, единственными кандидатами на <tex>j</tex>-активные позиции остаются <tex>(j-1)</tex>-активные позиции и <tex>j</tex>.
Далее, заметим, что если <tex>1\leq p\leq j-1</tex> — <tex>\mathrm{a}(j-1)</tex>-активная позиция и <tex>T[p'..j-1]</tex> — префикс <tex>T[p..j-1]</tex>, то <tex>p'</tex> тоже является <tex>(j-1)</tex>-активной. Если это не так, тогда существует позиция <tex>p'',\ p'<p''<j-1</tex>, такая, что <tex>T[p'..j-1]\prec T[p''..j-1]</tex>, и из этого следует, что <tex>T[p..j-1]=T[p'..j-1]T[j+p-p'..j-1]\prec T[p''..j-1]</tex>, противоречие. <tex>\mathrm{A}(j-1)</tex>-активная позиция <tex>p</tex> не является <tex>j</tex>-активной только если (1) <tex>T[j]\geq T[p]</tex> или (2) существует <tex>p<p'\leq j-1</tex> такая, что <tex>T[p'..j-1]</tex> — префикс <tex>T[p..j-1]</tex>, т.е. <tex>p'</tex> — <tex>(j-1)</tex>-активна и <tex>T[p'..j]\succ T[p..j]</tex> или, другими словами, <tex>T[j]>T[j+p-p']</tex>. Оба этих случая выявляются процедурой удаления.
}}
'''''Пример:''''' Если <tex>T[1..9]=dcccababb</tex>, то 8-активными позициями будут: 1, 2, 3, 4, 6, 8, и 9-активными позициями будут: 1, 2, 3, 4, 8, 9, т.е. мы добавляем 9 в наш список 8-активных позиций, а затем удаляем 6.
==Ссылки==
*[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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Основные определения. Простые комбинаторные свойства слов]]
