Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Поиск подстроки в строке с помощью хеш-функции
Раздел: Рефераты по информатике, программированию
Тип: доклад Добавлен 18:37:16 12 марта 2005 Похожие работы
Просмотров: 324 Комментариев: 10 Оценило: 5 человек Средний балл: 4.8 Оценка: неизвестно     Скачать

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

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
НЕТ ДЕВУШКИ? НЕ ТУПИ! ЧЕРЕЗ ЧАС БУДЕТ! https://is.gd/VOSao8 (копируй ссылку и переходи!)
Яна20:45:08 27 июня 2019Оценка: 5 - Отлично
Ребятки, кто на FAST-REFERAT.RU будет заказывать работу до 26го мая - вводите промокод iphone, и тогда будете учавствовать в розыгрыше iphone xs)) сам только что узнал, что у них такие акции бывают (п.с. кстати не удивляйтесь что вас перекидывает на сайт с другим названием, так и должно быть)
Макс10:58:47 19 мая 2019Оценка: 5 - Отлично
Здравствуйте! Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" работа...) - обращайтесь: VSE-NA5.RU Поможем Вам с выполнением учебной работы в самые короткие сроки! Сделаем все быстро и качественно. Предоставим гарантии!
Милена04:56:17 27 апреля 2019
Мне с моими работами постоянно помогают на FAST-REFERAT.RU - можете просто зайти узнать стоимость, никто вас ни к чему не обязывает, там впринципе всё могут сделать, вне зависимости от уровня сложности) у меня просто парень электронщик там какой то, тоже там бывает заказывает))
Настя10:45:49 03 декабря 2018
Спасибо, Оксаночка, за совет))) Заказал курсач, отчет по практике, 2 реферата и дипломную на REFERAT.GQ , все сдал на отлично, и нервы не пришлось тратить)
Алексей18:12:54 15 июля 2018Оценка: 5 - Отлично

Смотреть все комментарии (10)
Работы, похожие на Доклад: Поиск подстроки в строке с помощью хеш-функции

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(229673)
Комментарии (3125)
Copyright © 2005-2019 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru