Изменения

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

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

6 байт добавлено, 16:35, 2 мая 2015
м
Линейный алгоритм
Так как лист навсегда останется листом, зададим метку ребра ведущего в этот лист как <tex>s[j..x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.
Будем называть самым длинным не уникальным суффиксом суффикс, который заканчиватся на ребре и имеет максимальную длину из среди всех таких суффиксов. Заметим, что так как суффиксы, продленные по второму правилу, заканчиваются в листах и далее будут продляться за <tex>O(1)</tex>, то на очередной итерации мы можем начинать продлять суффиксы не с <tex>s[1..i-1]</tex>, а с самого длинного не уникального суффикса <tex>s[j^*..i-1]</tex>, т.е. суффикса на котором мы остановились на прошлой итерации, применив пустое правило продления. Следовательно, храня ссылку на место остановки на предыдущей итерации, мы можем не спускаться от корня к концу <tex>s[j^*..i-1]</tex> суффикса, а сразу продлевать его символом <tex>s_i</tex>.
=== Итоговая оценка времени работы ===
275
правок

Навигация