Изменения

Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_{1}s_{2}...\ldots s_{n}</tex>. На <tex>i</tex>-ой фазе неявное суффиксное дерево <tex>\tau_{i-1}</tex> для префикса <tex>s[1..\ldots i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1..\ldots i]</tex>. Достраивание происходит следующим образом: для каждого суффикса подстроки <tex>s[1..\ldots i-1]</tex> необходимо спуститься от корня дерева до конца этого суффикса и дописать символ <tex>s_i</tex>.

Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..\ldots i-1]</tex>.

|style="background:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в листе. Добавим <tex>s_{i}</tex> в конец подстроки, которой помечено ребро, ведущее в этот лист.

|style="background:#ffffff"|а) Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{i}</tex>. Создадим новый лист, в который из текущей вершины ведёт дуга с пометкой <tex>s_{i}</tex>.

|style="background:#ffffff"|б) Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается на ребре с меткой <tex>s[l..\ldots r]</tex> в позиции <tex>p-1(l \leqslant p \leqslant r)</tex> и <tex>s_{p} \ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>s[l..\ldots p-1]</tex> и <tex>s[p..\ldots r]</tex> и подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_{i}</tex>.

|style="background:#ffffff"|Пусть суффикс <tex>s[k..\ldots i-1]</tex> заканчивается в вершине, из которой есть путь по <tex>s_{i}</tex>. Тогда ничего делать не надо.

Рассмотрим внутреннюю вершину <tex>v</tex> с путевой меткой <tex>s[j..\ldots i]</tex>. Так как эта вершина внутренняя, её путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1..\ldots i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведёт в <tex> u</tex>.

Рассмотрим применение суффиксных ссылок. Пусть только что был продлён суффикс <tex>s[j..\ldots i-1]</tex> до суффикса <tex>s[j..\ldots i]</tex>. Теперь с помощью построенных ссылок можно найти конец суффикса <tex>s[j+1..\ldots i-1]</tex> в суффиксном дереве, чтобы продлить его до суффикса <tex>s[j+1..\ldots i]</tex>. Для этого надо пройти вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведёт путь, помеченный <tex>s[j..\ldots r]</tex>. У вершины <tex>v</tex> точно есть суффиксная ссылка (о том, как строятся суффиксные ссылки, будет сказано позже, а пока можно просто поверить). Эта суффиксная ссылка ведёт в вершину <tex>u</tex>, которой соответствует путь, помеченный подстрокой <tex>s[j+1..\ldots r]</tex>. Теперь от вершины <tex>u</tex> следует пройти вниз по дереву к концу суффикса <tex>s[j+1..\ldots i-1]</tex> и продлить его до суффикса <tex>s[j+1..\ldots i]</tex>.

Можно заметить, что подстрока <tex>s[j+1..\ldots i-1]</tex> является суффиксом подстроки <tex>s[j..\ldots i-1]</tex>. Следовательно, после перехода по суффиксной ссылке в вершину, помеченную путевой меткой <tex>s[j+1..\ldots r]</tex>, можно дойти до места, которому соответствует метка <tex>s[r+1..\ldots i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.

Легко увидеть, что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Поэтому осталось сказать, как построить суффиксные ссылки для созданных вершин. Рассмотрим новую внутреннюю вершину <tex>v</tex>, которая была создана в результате продления суффикса <tex>s[j..\ldots i-1]</tex>. Вместо того, чтобы искать, куда должна указывать суффиксная ссылка вершины <tex>v</tex>, поднимаясь от корня дерева для этого, перейдем к продлению следующего суффикса <tex>s[j+1..\ldots i-1]</tex>. И в этот момент можно проставить суффиксную ссылку для вершины <tex> v</tex>. Она будет указывать либо на существующую вершину, если следующий суффикс закончился в ней, либо на новую созданную. То есть суффиксные ссылки будут обновляться с запаздыванием. Внимательно посмотрев на все три правила продления суффиксов, можно осознать, что для вершины <tex> v </tex> точно найдётся на следующей фазе внутренняя вершина, в которую должна вести суффиксная ссылка.

Заметим, что на пути <tex>A</tex> в дереве по суффиксу <tex>s[j+1..\ldots i]</tex> не более чем на одну вершину меньше, чем на пути <tex>B</tex> по суффиксу <tex>s[j..\ldots i]</tex>. Каждой вершине <tex>v</tex> на пути <tex>B</tex> соответствует вершина <tex>u</tex> на пути <tex>A</tex>, в которую ведёт суффиксная ссылка. Разница в одну вершину возникает, если первому ребру в пути <tex>B</tex> соответсвует метка из одного символа <tex>s_{j}</tex>, тогда суффиксная ссылка из вершины, в которую ведёт это ребро, будет вести в корень.

При использовании правила продолжения 3 путь, помеченный <tex>s[j..\ldots i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1..\ldots i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1,\ j+2, \ldots, i</tex>.

Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j..\ldots x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.

Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k,\ k \leqslant i</tex>, а не от <tex>1</tex> до <tex>i</tex>. Действительно, если суффикс <tex>s[j..\ldots i-2]</tex> был продлён до суффикса <tex>s[j..\ldots i-1]</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j..\ldots i]</tex> по листовой вершине. Поэтому после применения правила 3 на суффиксе <tex>s[k..\ldots i]</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* = k</tex>.