• Новости
  • Темы
    • Экономика
    • Здоровье
    • Авто
    • Наука и техника
    • Недвижимость
    • Туризм
    • Спорт
    • Кино
    • Музыка
    • Стиль
  • Спецпроекты
  • Телевидение
  • Знания
    • Энциклопедия
    • Библия
    • Коран
    • История
    • Книги
    • Наука
    • Детям
    • КМ школа
    • Школьный клуб
    • Рефераты
    • Праздники
    • Гороскопы
    • Рецепты
  • Сервисы
    • Погода
    • Курсы валют
    • ТВ-программа
    • Перевод единиц
    • Таблица Менделеева
    • Разница во времени
Ограничение по возрасту 12
KM.RU
Рефераты
Главная → Рефераты → Информатика, программирование
  • Новости
  • В России
  • В мире
  • Экономика
  • Наука и техника
  • Недвижимость
  • Авто
  • Туризм
  • Здоровье
  • Спорт
  • Музыка
  • Кино
  • Стиль
  • Телевидение
  • Спецпроекты
  • Книги
  • Telegram-канал

Поиск по рефератам и авторским статьям

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

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

Каждый символ имеет свой уникальный код от 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/

Дата добавления: 10.03.2005

База рефератов на портале KM.RU существует с 1999 года. Она пополнялась не только готовыми рефератами, докладами, курсовыми, но и авторскими публикациями, чтобы учащиеся могли использовать их и цитировать при самостоятельном написании работ.


Это популяризирует авторские исследования и научные изыскания, что и является целью работы истинного ученого или публициста. Таким образом, наша база - электронная библиотека, созданная в помощь студентам и школьникам.


Уважаемые авторы! Если Вы все же возражаете против размещения Вашей публикации или хотите внести коррективы, напишите нам на почту info@corp.km.ru, мы незамедлительно выполним Вашу просьбу или требование.


официальный сайт © ООО «КМ онлайн», 1999-2025 О проекте ·Все проекты ·Выходные данные ·Контакты ·Реклама
]]>
]]>
Сетевое издание KM.RU. Свидетельство о регистрации Эл № ФС 77 – 41842.
Мнения авторов опубликованных материалов могут не совпадать с позицией редакции.

Мультипортал KM.RU: актуальные новости, авторские материалы, блоги и комментарии, фото- и видеорепортажи, почта, энциклопедии, погода, доллар, евро, рефераты, телепрограмма, развлечения.

Карта сайта


Подписывайтесь на наш Telegram-канал и будьте в курсе последних событий.


Организации, запрещенные на территории Российской Федерации
Telegram Logo

Используя наш cайт, Вы даете согласие на обработку файлов cookie. Если Вы не хотите, чтобы Ваши данные обрабатывались, необходимо установить специальные настройки в браузере или покинуть сайт.