|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 04 Jan 2002 16:55:32
To : Andrew Simontsev
Subject : Строки...
--------------------------------------------------------------------------------
AS> Интересно, есть ли какой-нибудь алгоритм для решения следущей
AS> задачи: есть длинная-длинная строка X, надо найти минимальную строку Y,
AS> которая гарантированно не является подстрокой X? Может кто-нибудь знает?..
Если долго не думать :) и памяти не жалеть, то можно построить суффиксное
дерево этой строки (O(n)), потом, просматривая его от корня уровень за уровнем,
найти узел, у которого число потомков меньше мощности алфавита, и дописать любой
из отсутствующий среди его потомков символ в конец подстроки, соответствующей
этому узлу.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Строки... 
