Изменения

[[Файл:image001.png|Рис. 1. Схематичная иллюстрация к Лемме 11.|800px]]

Таким образом, <tex>T[\mu..j]=\rho^{r}\rho'</tex>. Если <tex>t>r</tex>, тогда <tex>\rho^{t}\rho'\succ\rho^{r}\rho'</tex>, поэтому <tex>T[\mu..j]</tex> {{---}} длиннейший суффикс строки <tex>T[i..j]</tex>, равный <tex>\rho^{t}\rho'</tex> для некоторого <tex>t</tex>.

'''Рис. 2''' Разбиения <tex>[</tex>1, <tex>j]</tex> на <tex>R_{j}^{\ell}</tex> при <tex>j=27</tex> и <tex>j=28</tex>. При <tex>j=28</tex>, <tex>k=2</tex> и <tex>2k+4=8,\ R_{27}^{7}</tex> и <tex>R_{27}^{8}</tex> объединяются в <tex>R_{28}^{8}</tex>. На самом деле, все длины <tex>|R_{j}^{\ell}|</tex> являются степенями двойки, но наш алгоритм не использует это наблюдение.

Мы просматриваем позиции строки <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> lcp <tex>(T[p_{z}..],\ T[p_{z+1}..])</tex> и с этого момента наименьший <tex>j'=p_{z}+L</tex>, когда одна из них должна быть удалена из списка, и вставляем указатель на пару <tex>p_{z},\ p_{z+1}</tex> в j'-й лист. Когда мы действительно достигнем <tex>j=j'</tex>, мы проследуем по указателю и проверим, что <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем.