Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

52 байта добавлено, 13:28, 15 апреля 2015
м
Линейный алгоритм
}}
Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, зададим метку ребра ведущего в этот лист как <tex>s[i..nx]</tex>, где <tex>nx</tex> {{---}} это длина исходного текстассылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>i</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.
=== Итоговая оценка времени работы ===
275
правок

Навигация