|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Krylov 2:5020/400 05 Jul 2003 15:55:02
To : All
Subject : Хитрый поиск подстроки
--------------------------------------------------------------------------------
Привет всем!
Известен ли вам алгоритм, позволяющий определить факт существования
подстроки в строке?
Hе позицию, а именно существование подстроки в строке?
Кажется, такой алгоритм не будет требовать хранения всей строки - а только
некоей её "свертки",
которая позволит определить, есть ли подстрока в исходной строке.
Правда, сразу же приходит на ум контрпример - если искать при помощи этой
"свертки" подстроку с
такой же как у исходной строки длинной, то перебором можно получить
всё-таки исходную строку,
а значит, в этой "свертке" содержится информации не меньше, чем в исходной
строке.
Удачи!
Крылов Дмитрий
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
