Изменения
Нет описания правки
===Компромисс===
===Применение===
==Поиск максимального суффикса==
Наша структура данных, необходимая для поиска максимального суффикса, очень похожа на ту, что мы разработали для минимального суффикса. Однако, в отличие от той проблемы, свойства максимальных суффиксов позволят нам добиться линейной асимптотики.
Заметим, что единственный компонент из части о минимальном суффиксе, который не может быть сразу адаптирован к задаче о максимальном
суффиксе, это Лемма 1. Так как эта лемма неприменима к нашей задаче, далее мы докажем следующую лемму, эквивалентную в смысле
алгоритмического приложения.
Канонические подстроки <tex>S_{j}^{\ell}</tex> обозначены как и ранее.
{{Лемма
|author=7
|id=lemma
|statement= Рассмотрим подстроку <tex>T[i..j]</tex>. Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> можно найти индекс <tex>p(i\leq p\leq j)</tex> такой, что максимальный суффикс <tex>T[\mu..j]</tex> строки <tex>T[i..j]</tex> равен либо
<tex>(a)T[p..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 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:
}}
{{Теорема
|id=theorem
|author=8
|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..j]</tex> of <tex>T[i..j]</tex> короче, чем <tex>S_{j}^{\alpha(i,j)}</tex> (случай (b) Леммы 7), алгоритм может вернуть любое <tex>p\in[i,\ j]</tex>. Далее мы предполагаем, что <tex>T[\mu..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..j]</tex>, начинающихся с позиций в промежутке <tex>[i,\ r]</tex>, отличаются не более чем в два раза.
Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 1]
}}
{{Лемма
|id=lemma
|author=9
|statement= Пусть <tex>P_{1}=T[p_{1}..j]</tex> — префикс строки <tex>T[\mu..j]</tex> и пусть <tex>P_{2}=T[p_{2}..j]</tex>, где <tex>T[p_{2}..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..j]</tex>.
|proof= Пусть <tex>T[p_{1}..]</tex> — максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..]</tex> — максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1}..j]</tex> является префиксом строки <tex>T[\mu..j]</tex>. Предположим, что <tex>P_{1}</tex> — префикс (иначе <tex>P_{2} \ p_{1}=\mu\</tex> по Лемме 9). Длины <tex>P_{1}</tex> и <tex>P_{2}</tex> различаются не более чем в два раза, поэтому <tex>2|P_{1}|\geq|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 1], но здесь мы приводим доказательства вследствие другого обозначения.
}}
==Ссылки==
