|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 05 Jul 2003 22:33:18
To : Dmitriy Krylov
Subject : Хитрый поиск подстроки
--------------------------------------------------------------------------------
DK> Известен ли вам алгоритм, позволяющий определить факт существования
DK> подстроки в строке?
DK> Hе позицию, а именно существование подстроки в строке?
DK> Кажется, такой алгоритм не будет требовать хранения всей строки - а
DK> только некоей её "свертки",
DK> которая позволит определить, есть ли подстрока в исходной строке.
DK> Правда, сразу же приходит на ум контрпример - если искать при помощи
DK> этой "свертки" подстроку с такой же как у исходной строки длинной, то
DK> перебором можно получить всё-таки исходную строку, а значит, в этой
DK> "свертке" содержится информации не меньше, чем в исходной строке.
Эта "свертка" называется суффиксным деревом. Она дает ответ одновременно на
оба вопроса (о существовании и позиции подстроки) за время, не большее
пропорционального длине подстроки. Ясное дело, при предварительном построении за
время, пропорциональное длине исходной строки. Hо действительно, с точки зрения
размеров это скорее не свертка, а "развертка". :)
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Хитрый поиск подстроки 
