|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 05 Jan 2002 07:16:03
To : Serge Nozhenko
Subject : Re: Строки...
--------------------------------------------------------------------------------
До меня дошли слухи, что *04.01.02* *15:55:32* пролетало сообщение
от Serge к *Andrew Simontsev* про *"Строки..."*. И я решил вмешаться.
AS>> Интересно, есть ли какой-нибудь алгоритм для решения следущей
AS>> задачи: есть длинная-длинная строка X, надо найти минимальную строку Y,
AS>> которая гарантированно не является подстрокой X? Может кто-нибудь
AS>> знает?..
SN> Если долго не думать :) и памяти не жалеть, то можно построить
SN> суффиксное дерево этой строки (O(n)), потом, просматривая его от корня
SN> уровень за уровнем, найти узел, у которого число потомков меньше мощности
SN> алфавита, и дописать любой из отсутствующий среди его потомков символ в
SN> конец подстроки, соответствующей этому узлу.
Hе поделишься инфой, что такое суффиксное дерево?
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: RAP - кал, слушай металл. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
