|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.04.2011, 16:41 | #1 |
Пользователь
Регистрация: 23.02.2011
Сообщений: 28
|
Поиск подстроки в строке
Поиск подстроки в строке с помощью хеша
Я нашел очень интересную статью и не могу его реализовать практически на java, или может кто-то пользовался этим алгоритмом и написал ? Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный. Я рассмотрю метод поиска с помощью хеш-функции - достаточно простой и быстрый. Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа. Пример: Алфавит кодов: Q = 1 W = 2 E = 3 R = 4 T = 5 Y = 6 Подстрока: QWERTY Строка: QWERYTEWEQWERTY Считаем хэш-функцию для подстроки: SS = 1+2+3+4+5+6+7 = 28 QWERYTEWEQWERTY Считаем хэш-функцию для первых 6 символов строки: FS = 1+2+3+4+5+7+6 = 28 Проводим полное сравнение строк - строки не совпадают. QWERYTEWEQWERTY FS = 28 - [Q] + [E] = 28 - 1 + 3 = 30 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 30 - [W] + [W] = 30 - 2 + 2 = 30 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 30 - [E] + [E] = 30 - 3 + 3 = 30 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 30 - [R] + [Q] = 30 - 4 + 1 = 27 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 27 - [Y] + [W] = 27 - 6 + 2 = 23 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 23 - [T] + [E] = 23 - 5 + 3 = 21 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 21 - [E] + [R] = 21 - 3 + 4 = 22 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 22 - [W] + [T] = 22 - 2 + 5 = 25 - код не совпадает, сравнение не проводим. QWERYTEWEQWERTY FS = 25 - [E] + [Y] = 25 - 3 + 6 = 28 - код совпадает, полное сравнение совпадает. Ура Продолжение здесь http://g6prog.narod.ru/findstr.html Последний раз редактировалось videolord; 10.04.2011 в 09:14. |
10.04.2011, 01:00 | #2 |
Участник клуба
Регистрация: 15.07.2008
Сообщений: 1,933
|
Вот накидал:
Код:
|
10.04.2011, 09:11 | #3 |
Пользователь
Регистрация: 23.02.2011
Сообщений: 28
|
Классно!!! Спасибо огромное вам netrino!!!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск подстроки в строке | valdemar593 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 03.06.2010 21:42 |
C++ Поиск подстроки в строке по маске | Ханако Сейсин | Помощь студентам | 0 | 29.04.2010 14:36 |
поиск подстроки в строке!!! | StoneSour | Общие вопросы C/C++ | 2 | 15.03.2010 21:31 |
Задача Delphi 7 - Замена подстроки в строке | Юрий2009 | Помощь студентам | 3 | 23.04.2009 10:12 |
Найти позицию подстроки в строке | Ozerich | Общие вопросы C/C++ | 5 | 15.12.2008 16:06 |