262
правки
Изменения
→Поиск лексикографически минимального суффикса строки
|id=lemma
|author=1
|statement= Минимальный суффикс <tex>T[i..j]</tex> равен либо <tex>(a)\ T[p..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] минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leq\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канониеских подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..j]</tex> является минимальным суффиксом <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется первый случай из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> - одна из базовых операций, поддерживаемых улучшенным суфмассивом.
}}
Предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex> c <tex>\alpha(i,\ j)=\ell</tex>. Наш подход основан на Лемме 1. Если выполняется её первый случай, лемма позволяет нам вычислить ответ за <tex>\mathcal{O}(1)</tex>. В общем случае, мы найдём минимальный суффикс <tex>S_{j}^{\ell}</tex>, сравним его с <tex>T[p..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>\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..j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом - найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leq\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'\leq k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что<tex>\tau k\leq\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>.
{{Теорема
