Работа выполнена досрочно. Все необходимые замечания были исправлены моментально. Хорошая работа!
Иван
ТУСУР
Узнайте стоимость индивидуальной работы
это быстро и бесплатно
Оформите заказ сейчас и получите скидку 100 руб.!
Готовые работы
/
Рефераты
/ Информатика и программирование
/ Поиск подстроки в строке с помощью хеш-функции
Поиск подстроки в строке с помощью хеш-функции
Тип
Реферат
Предмет
Информатика и программирование
Просмотров
1396
Размер файла
13 б
Поделиться
Ознакомительный фрагмент работы:
Поиск подстроки в строке с помощью хеш-функции
Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный. Я рассмотрю метод поиска с помощью хеш-функции - достаточно простой и быстрый.
Каждый символ имеет свой уникальный код от 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.
Нет нужной работы в каталоге?
Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников 
Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.
Цены ниже, чем в агентствах и у конкурентов
Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит
Бесплатные доработки и консультации
Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки
Гарантируем возврат
Если работа вас не устроит – мы вернем 100% суммы заказа
Техподдержка 7 дней в неделю
Наши менеджеры всегда на связи и оперативно решат любую проблему
Строгий отбор экспертов
К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»
1 000 +
Новых работ ежедневно
Требуются доработки?
Они включены в стоимость работы 
Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован 
Иванна
Математика
История
Экономика
159599
рейтинг
рейтинг
3275
работ сдано
работ сдано
1404
отзывов
отзывов
Ludmila
Математика
Физика
История
156492
рейтинг
рейтинг
6068
работ сдано
работ сдано
2737
отзывов
отзывов
Svetlana
Химия
Экономика
Биология
105734
рейтинг
рейтинг
2110
работ сдано
работ сдано
1318
отзывов
отзывов
Константин Николаевич
Высшая математика
Информатика
Геодезия
62710
рейтинг
рейтинг
1046
работ сдано
работ сдано
598
отзывов
отзывов
Отзывы студентов о нашей работе
63 769 оценок
среднее 4.9 из 5
Иван
ТУСУР
Работа выполнена досрочно. Все необходимые замечания были исправлены моментально. Хорошая ...
Елена
КГСХА
Роберт большое вам спасибо! Все сделали очень быстро!!! Всем советую. Быстро, качественно,...
Yana_Abd
ЮУрГУ
Получила отлично за выполненную Ириной работу у очень придирчивого препода
Роберт большое вам спасибо! Все сделали очень быстро!!! Всем советую. Быстро, качественно, надежно!!!!!
Елена
КГСХА
Получила отлично за выполненную Ириной работу у очень придирчивого препода
Yana_Abd
ЮУрГУ
Последние размещённые задания
Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн 
только что
Доработать Контрольную работу
Контрольная, Основы инженерной геологии и гидрогеологии
Срок сдачи к 11 янв.
только что
Уважаемые авторы! прошу решить рар по статистике творческое задание. часть 2. по критерию пирсона проверить гипотезу о нормальном распределении генеральной совокупности.
Контрольная, Статистика
Срок сдачи к 16 дек.
только что
только что
1 минуту назад
«Технология выполнения женской стрижки и окрашивания волос с...
Диплом, Технологическая парикмахерского искусства
Срок сдачи к 26 дек.
1 минуту назад
1 минуту назад
1 минуту назад
1 минуту назад
Выполнить лабораторные работы в системе Miro
Лабораторная, Проектирование безопасных систем, программирование
Срок сдачи к 17 дек.
1 минуту назад
Задание СРМ ( общая схема составления расписания)
Другое, Математическое моделирование
Срок сдачи к 15 дек.
3 минуты назад
Расчётно-графическое задание проектирование ЛВС
Контрольная, Телекоммуникационные системы. ИНФОРМАТИКА
Срок сдачи к 10 янв.
3 минуты назад
Сделать дневник по практике
Отчет по практике, Стоматология хирургическая, медицина
Срок сдачи к 30 дек.
4 минуты назад
Написать статью для публикации на тему "Удовлетворенность трудом персонала как фактор развития кадрового потенциала организации"
Статья, Управление персоналом
Срок сдачи к 19 дек.
4 минуты назад
Сделать презентацию и написать доклад к ней
Презентация, Спортивная дефектология
Срок сдачи к 17 дек.
4 минуты назад
Необходимо выполнить расчет , вариант 61.
Решение задач, Основы расчета строительных конструкций, строительство
Срок сдачи к 15 дек.
4 минуты назад
Выполнить и оформить работу в соответствии с требованиями.
Контрольная, Схемотехника
Срок сдачи к 22 дек.
4 минуты назад
4 минуты назад
Закажи индивидуальную работу за 1 минуту!
Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.
«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами
Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:
Мы ВКонтакте 
Трейлер о сайте
Принимаем к оплате
© 2011—2025 Всё сдал!