|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 06 Jan 2002 17:09:26
To : Sergey Politov
Subject : Строки...
--------------------------------------------------------------------------------
SP> если я правильно понял твое объянение, что такое суффиксное дерево, то у
Видимо, неправильно. :)
SP> тебя не совсем правильное решение. Если ты выдаешь только два
SP> символа, то у тебя не всегда такая строка будет найдена. Тут кстати
SP> возникает задача, какова минимальная длина такое строки. Если же ты
SP> выдаешь все последовательность начиная с корня,
Конечно, всю последовательность.
SP> то она не всегда будет наикратчайшей.
Почему не будет? Узлы в trie соответствуют различным префиксам строк, из
которых оно построено. Узлы суффиксного дерева соответствуют подстрокам исходной
строки. Обходя дерево уровень за уровнем, мы просматриваем все существующие
подстроки, начиная с самых коротких. Собственно, сами подстроки просматривать не
надо, достаточно сравнить их число с мощностью алфавита. Как только в каком-то
узле получается "меньше" - его и надо смотреть подробно.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
