|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Simontsev 2:5005/115.41 05 Jan 2002 20:02:33
To : Vadim Meshkov
Subject : Строки...
--------------------------------------------------------------------------------
Saturday, January 05 2002 13:38, Vadim Meshkov wrote to Andrew Simontsev:
AS>> Интересно, есть ли какой-нибудь алгоритм
AS>> для решения следущей задачи:
AS>> есть длинная-длинная строка X, надо найти
AS>> минимальную строку Y, которая
AS>> гарантированно не является подстрокой X? Может
AS>> кто-нибудь знает?..
VM> Hе знаю, что такое "суффиксное дерево", но если
VM> требование "минимальности" не жесткое, то можно
VM> предложить простые алгоритмы, которые находят строку Y
VM> достаточно короткую. Hапример такие два.
[...]
VM> Трудоемкость обоих алгоритмов --- порядка N сравнений
VM> (N --- длина строки). Полагаю, что со вторым алгоритмом
VM> даже для строки в 5Мб получится слово не более чем из 5-
VM> 7 букв.
VM> Годится?
Спасибо, достаточно красивые решения...
Bye, Vadim.
Sincerely yours, Andrew.
Играет: Ramones - Scattergun ("!Adios Amigos!") [Stopped]
... I'm a VooDoo Chile!
--- Добрых дел мастер 3.0.1 лет ----------------------------------
* Origin: Меняю комнатную собачку на двухкомнатную. (2:5005/115.41)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
