Изменения
→Поиск лексикографически максимального суффикса строки
|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}</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://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6], но здесь мы приводим доказательства вследствие другого обозначения.
}}
Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[</tex>1, <tex>j]</tex> на диапазоны <tex>R_{j}^{\ell}</tex>. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что <tex>B_{j}[\ell]=1</tex> только когда l-й счетчик не равен нулю. Чтобы эффективно обновить список <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}..],\ T[p_{z+1}..])</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 и процесс, который мы описали, эквивалентны.
