пошуку рядка в рядку за допомогою хеш-функції
Пошук
підрядка в рядку - часто виникає на практиці завдання. Алгоритм пошуку рядка в
рядку звичайної підстановкою до кожної позиції рядка всій підрядка - метод
неефективний і взагалі сумний. Я розгляну метод пошуку за допомогою хеш-функції
- Досить простий і швидкий.
Кожен
символ має свій унікальний код від 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 - код співпадає, повне порівняння збігається.
Ура!
Текст
програми:
Program
FSISHF; (пошуку підрядка в рядку)
Const
NStr = 30000;
NSub = 3000;
Var
FStr: array [1 .. NStr] of char;
FSub: array [1 .. NSub] of char; (substring)
FSum, NSum: longint; (Контрольна сума)
Spec, Work: word;
Flag: boolean;
Begin
FSum: = 0;
NSum: = 0;
FillChar (FStr, SizeOf (FStr), 0);
FillChar (FSub, SizeOf (FSub), 0);
For Spec: = 1 to NSub do
FSum: = FSum + Ord (FSub [Spec ]);
For Spec: = 1 to NSub do
NSum: = NSum + Ord (FStr [Spec ]);
For Spec: = NSub to NStr do begin
If NSum = FSum then begin
Flag: = true;
For Work: = 1 to NSub do
If FSub [Work] FStr [Spec - NSub
+ Work] then begin
Flag: = false;
break;
end;
If Flag = true then begin
Writeln ( 'substring starts at position:
', Spec - NSub);
Halt;
end;
end;
NSum: = NSum + Ord (FStr [Spec + 1]) - Ord (FStr [Spec - NSub + 1 ]);
end;
Writeln ( 'no such substring');
end.
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://g6prog.narod.ru/
