Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

Поиск подстроки в строке с помощью хешфункции

Поиск подстроки в строке с помощью хешфункции.
Поиск подстроки в строке с помощью хеш-функции
Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный. Я рассмотрю метод поиска с помощью хеш-функции - достаточно простой и быстрый.

Пример:
Алфавит кодов:
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/
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?