Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный. Я рассмотрю метод поиска с помощью хеш-функции - достаточно простой и быстрый.
Каждый символ имеет свой уникальный код от 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.
Другие работы по теме:
«Функции языка Visual Basic. Выражения»
Если компьютер включен и Бейсик загружен, можно смело приступить к работе. Начнем с того, что вы хотите что-то вычислить. Бейсик для этого лучше, чем любой калькулятор. Наберите команду
Теорема Лапласа
Теоре?ма Лапла?са — одна из теорем линейной алгебры. Названа в честь французского математика Пьера-Симона Лапласа (1749 — 1827), которому приписывают формулирование этой теоремы в 1772 году.
Решение матриц
Правила произведения матрицы и вектора, нахождения обратной матрицы и ее определителя. Элементарные преобразования матрицы: умножение на число, прибавление, перестановка и удаление строк, транспонирование. Решение системы уравнений методом Гаусса.
Методы Хука-Дживса
Метод Хука-Дживса, модифицированный метод Хука-Дживса, блок-схема, результаты работы программы.
Основы высшей матиматики
Вычисление определителя 4-го порядка, математическое решение системы методами матрицы, Крамера и Гаусса. Характеристика понятий невырожденной и обратной, транспонированной и присоединенной матрицы, нахождение алгебраических дополнений элементов таблицы.
Системы линейных уравнений
Решение системы линейных уравнений по правилу Крамера и с помощью обратной матрицы. Нахождение ранга матрицы. Вычисление определителя с помощью теоремы Лапласа. Исследование на совместимость системы уравнений, нахождение общего решения методом Гауса.
Обработка строк в РНР
Одной из наиболее часто встречающихся задач в программировании является обработка символьных последовательностей. Если проще – строк. Как это делается на языке гипертекстового препроцессора РНР и есть тема этой статьи.
Команды системного администратора
В этой статье собраны основные команды прописываемые в командной строке Windows NT/2000/XP для выполнения определенной сетевой функции.
Построение формального языка L
Построение формального языка WHILE( , ...])>]; WHILE - входной терминальный символ - условное выражение - некоторая функция, которая может отсутствовать
Команды Norton Commander
Кафедра проектирования дорог Лабораторная работа №1 по курсу «Информатика» Выполнил студент группы №114359 Райхман Сергей Юрьевич роверил Минск 1999
Обработка одномерных массивов в среде программирования Lazarus
Форма программы для ввода и вывода массива в программной среде Lazarus. Характеристика главных недостатков Lazarus. Цикл для пропуска пробелов между словами. Результат обработки текстового редактора memo.text. Листинг и экранные формы заданной программы.
Алгоритмы поиска подстроки в строке
Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.
Строковый тип данных в языке Pascal
Ознакомимся с типом данных, который относится к числу структурированных. Это строковый тип данных (строка). Строка — это последовательность символов. Каждый символ занимает 1 байт памяти (код ASCII).
Базы данных и базы знаний
Формирование основных таблиц базы данных деканата и устанавливание к ним ключей. Заполнение баз необходимыми сведениями. Формулировка схем данных форм и запросов. Настройка некоторых запросов по своим свойствам. Создание форм через "мастера форм".
Алгоритмы поиска подстроки в строке
Теоретические сведения об алгоритмах поиска подстроки в строке. Глобализация информации в сети Internet. Интеллектуальный поиск. Алгоритм последовательного (прямого) поиска, Рабина и их применение. Анализ алгоритмов. Реализация программного кода.
Вопросы по информатике
В чем состоят особенности организации пакетного режима работы ЭВМ. Сформировать файл, содержащий результаты сессии студентов одной группы в виде матрицы.
Регулярные выражения в perl
Регулярные выражения являются наиболее сложной темой практически для любого программиста: как для новичка, только что начавшего изучать perl, так и для опытного программиста, ранее не встречавшегося с регулярными выражениями.
Подготовка электронных документов в MS Word 2
НОУ ВПО ТУЛЬСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ И БИЗНЕСА им. Н. Д. Демидова ОТЧЕТ о выполнении компьютерного практикума по дисциплине “Информатика” “Подготовка электронных документов в MS Word”
Электронные таблицы, назначение и основные функции
Электронные таблицы (или табличные процессоры) — это прикладные программы, предназначенные для проведения табличных расчетов. В электронных таблицах вся обрабатываемая информация располагается в ячейках прямоугольной таблицы. Отличие электронной таблицы от простой заключается в том, что в ней есть «поля» (столбцы таблицы), значения которых вычисляются через значения других «полей», где располагаются исходные данные.
Контрольная работа по Информатике 9
Задание № 1 Вычислить функцию, используя стандартные функции (значения аргументов установить самостоятельно). Решение: =КОРЕНЬ(D4). =СТЕПЕНЬ(D4;2)+СТЕПЕНЬ(E4;2)-50+КОРЕНЬ(50)+D4-8.071+КОРЕНЬ(8.071).
Программа текстовый редактор
Программа "текстовый редактор" Пояснительная записка к курсовой работе по дисциплине “Основы алгоритмизации и программирования” Выполнил : студент гр. 96-ВВ3 Курапов А.В.
Команды Norton Commander
ФТК Кафедра проектирования дорог Лабораторная работа №1 по курсу «Информатика» Выполнил студент группы №114359 Райхман Сергей Юрьевич роверил Минск 1999
Базы данных и базы знаний
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени Р.Е. Алексеева Кафедра «Компьютерные технологии в проектировании и производстве» Дисциплина «Базы данных и базы знаний»
Команды системного администратора
В этой статье собраны основные команды прописываемые в командной строке Windows NT/2000/XP для выполнения определенной сетевой функции. Пример вида <имя> ,практически пишется как имя. Чтобы запустить командную строку необходимо нажать Пуск - Выполнить ввести "cmd" Enter или OK.
Строковые переменные
Введение Типы данных При решении задач в программировании выполняется обработка информации различного характера. Это могут быть целые и дробные величины, строки и другое. Соответственно константы и переменные должны быть описаны как целые, дробные, строковые и т.д.
