262
правки
Изменения
м
Будем обозначать <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> найти [http://en.wikipedia.org/wiki/LCP_array наибольший общий префикс] <tex>lcp(x,y)</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>
Чтобы получить структуру данных, со временем построения <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'\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>.
{{Теорема
