Узнай об автоматике все - читай kip-help.narod.ru

Хочешь узнать ответ

на свой вопрос?

Напиши в редакцию!

Теория и практика

электроники

Суть метода заключается в следующем: для подстроки считается некоторая хэш-функция (например сумма кодов всех символов подстроки), затем по той же формуле считается хэш-функция для части строки, равной по длине подстроке. В случае совпадения хэш-функций, сравнивают подстроку и взятую часть строки для окончательной проверки. Ускорение работы алгоритма связано с тем, что мы можем использовать рекуррентные вычисления для нахождения хэш-функции (отнимаем от функции значение самого "старого" символа и добавляем значение следующего символа).

Алгоритм:

Пример:

Пусть в строке используются символы A B C D E F

Поставим в соответствие символам числовые значения:

A=1

B=2

C=3

D=4

E=5

F=6

Пусть в строке AEDABCBADF требуется найти слово BAD

Будем вычислять значение хэш-функции как простую сумму числовых значений символов.

Считаем для слова BAD хэш-функцию:

BAD=2+1+4=7

1) Берем первые 3 символа строки и считаем хэш-функцию для них:

AED=1+5+4=10 хэш-функции не совпадают, сравнение не проводим

Чтобы посчитать новое значение хэш-функции (для трех символов, начиная со второго) - отнимаем от старого значения хэш-функции значение первого символа и прибавляем значение четвертого символа:

2) EDA=8-1+1=10 хэш-функции не совпадают, сравнение не проводим

3) DAB=10-5+2=7 хэш-функции совпадают, проводим посимвольное сравнение, выясняем, что подстроки не совпадают

4) ABC=7-4+3=6 хэш-функции не совпадают

5) BCB=6-1+2=7 хэш-функции совпадают, проводим посимвольное сравнение, выясняем, что подстроки не совпадают

6) CBA=7-2+1=6 хэш-функции не совпадают

7) BAD=6-3+4 хэш-функции совпадают, проводим посимвольное сравнение, выясняем, что подстроки совпадают => подстрока находится в строке начиная с седьмой позиции.

На практике выбирают различные методы и формулы для вычисления хэш-функций.

Теория информации

и автоматического

управления

Метрология

Программирование

Заметки инженера

 Решебник

Научись самостоятельно изготавливать электронные устройства с сайтом  radiohlam.ru

ПОРА СТАНОВИТЬСЯ ЭЛЕКТРОНЩИКОМ

О сайте

Решим для вас задачи по математике, физике, тау, программированию...

Совершенно бесплатно. Подробности в разделе Решебник

© 2007 Материалы сайта охраняются законом об авторском праве