299
правок
Изменения
→Алгоритм Укконена за квадратичное время
Рассмотрим правила продолжения суффиксов.
При использовании правила 1 по [[#l1|лемме 1 ]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br />
При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br />
При использовании правила 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
