Изменения

|style="background:#ffffff"|''1. Продление листа''

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

|-

|style="background:#ffffff"|''2.1 Создание листа''

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

|-

|style="background:#ffffff"|''2.2 Ответвление''

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

|-

|style="background:#ffffff"|''3 Ничего не делать''

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

|}