|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Krylov 2:5020/400 06 Jul 2003 03:46:06
To : Serge Nozhenko
Subject : Re: Хитрый поиск подстроки
--------------------------------------------------------------------------------
Hello, Serge!
You wrote to Dmitriy Krylov on Sat, 05 Jul 2003 21:33:18 +0400:
DK>> Известен ли вам алгоритм, позволяющий определить факт существования
DK>> подстроки в строке?
DK>> Hе позицию, а именно существование подстроки в строке?
SN> Эта "свертка" называется суффиксным деревом. Она дает ответ
SN> одновременно на оба вопроса (о существовании и позиции подстроки) за
SN> время, не большее пропорционального длине подстроки. Ясное дело, при
SN> предварительном построении за время, пропорциональное длине исходной
SN> строки. Hо действительно, с точки зрения размеров это скорее не
SN> свертка, а "развертка". :)
Hу в том-то и дело.
Собственно, мне такой алгоритм нужен для поиска некоего слова по
документам.
Если документов куча - и все их запихнуть в это дерево, то тогда вроде
будет
экономия и дерево действительно будет занимать меньше места, чем все
документы...
Hадо попробовать.
With best regards,
Dmitriy Krylov
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Хитрый поиск подстроки 