Поделись:





РАЗДЕЛЫ
Авиация и космонавтика (292)
Административное право (113)
Английский язык (62064)
Арбитражный процесс (22)
Архитектура (98)
Астрология (15)
Астрономия (4788)
Банкосвкое дело (4987)
Без категории (14560)
Безопасность жизнедеятельности (2585)
Биографии (3219)
Биология (4036)
Биология и химия (1421)
Биржевое дело (61)
Ботаника и сельское хозяйство (2694)
Бухгалтерский учет и аудит (7694)
Валютные отношения (47)
Ветеринария (45)
Военная кафедра (732)
География (4779)
Геодезия (27)
Геология (1186)
Геополитика (42)
Государство и право (19449)
Гражданское право и процесс (434)
Делопроизводство (17)
Деньги и кредит (96)
ЕГЭ (32)
Естествознание (92)
Журналистика (899)
ЗНО (47)
Зоология (34)
Издательское дело и полиграфия (475)
Инвистиции (91)
Информатика (3452)
Информатика, программирование (5960)
Исторические личности (2109)
История (20812)
История техники (765)
Кибернетика (60)
Коммуникации и связь (3050)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (580)
Краткое содержание произведений (1000)
Криминалистика (102)
Криминология (46)
Кулинария (1147)
Культура и искусство (8212)
Культурология (501)
Литература (зарубежная) (2035)
Литература и русский язык (11459)
Логика и логстика (545)
Маркетинг (7739)
Медицина и здоровье (9936)
Международное право (79)
Международные отношения (2189)
Менеджмент (11960)
Металлургия (82)
Москвоведение (764)
Музыка (1307)
Налоги и налогооблажение (199)
Наука и техника (1139)
Начертательная геометрия (9)
Окультизм и уфология (8)
Педагогика (7566)
Политология (3650)
Право, юриспруденция (3708)
Предпринимательство (406)
Промышленность и производство (6865)
Психология (8363)
Психология и педагогика (4048)
Радиоэлектронника (364)
Реклама (948)
Религия и мифология (2829)
Риторика (23)
Сексология (748)
Социология (4709)
Статистика (80)
Страхование (105)
Строительство (1984)
Таможенная система (655)
Теория государства и права (219)
Теория организации (35)
Технология (492)
Транспорт (2552)
Туризм (80)
Уголовное право и процесс (369)
Управление (105)
Физика (3298)
Физкультура и спорт (4360)
Философия (6846)
Финансовые науки (4389)
Финансы (5237)
Химия (2195)
Цифровые устройства (22)
Экология (4322)
Экономика (19673)
Экономико-математическое моделирование (644)
Экономическая география (113)
Экономическая теория (2472)
Этика (887)
Юриспруденция (268)
Языковедение (135)
Языкознание и филология (1140)
Счетчики


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

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

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

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



Оценка: 0. | Оценило 0 человека.
ВНИМАНИЕ
Уважаемые гости, хотим обратить Ваше внимание на то, что все представленные работы на этом сайте получены с публичных ресурсов, находятся в свободном доступе, не являются уникальными и не подходят для их сдачи "как есть".
Если вы обладаете авторским правом на какую либо информацию, размещенную на нашем сайте и не согласны с её общедоступностью, обязательно сообщите нам об этом.
Данные работы Вы можете использовать в качестве дополнительных материалов для написания своего реферата либо любой другой работы.
В ПОМОЩЬ УЧАЩИМСЯ
Мы настоятельно рекомендуем нашим пользователям самостоятельно выполнять все работы. Но бывают ситуации, когда нет возможности, либо элементарно времени, чтобы самому заниматься той или иной работой. В этом случае можно заказать выполнение за вас реферата, курсовой и т.д. Но будет ли такая работа соответствовать всем вашим критериям? Сомневаемся. Поэтому хотим дать вам хороший совет. Найдите на нашем сайте работу, максимально подходящую под ваши критерии. Закажи повышение оригинальности и получите уникальную работу для сдачи. Это сэкономит вам деньги и вы получите именно то, что хотели.
НОВОСТИ НАУКИ
Обратная связь
По всем интересующим вас вопросам обращайтесьна почту:


Если у вас есть интересная работа и вы хотите ей поделиться, присылайте ее нам и мы обязательно разместим ее на нашем сайте, а пользователи обязательно скажут вам спасибо: