Пошук підрядка в рядку - часто виникає на практиці завдання. Пошук підрядка в рядку звичайної підстановкою до кожної позиції рядка всій підрядка - метод неефективний і взагалі сумний. Я розгляну метод пошуку за допомогою хеш-функції - досить простий і швидкий.
Кожен символ має свій унікальний код від 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.