Реферат: Алгоритмы поиска подстроки в строке

Введение

Цель курсовой работы:Изучить и проанализировать алгоритмы поиска подстроки в строке, и рассмотретьряд практических задач на данную тематику.

Задачи курсовой работы:изучить задачи связанные с проблемой поиска подстроки в строке, дать основныеопределения; рассмотреть применение различных алгоритмов поиска подстроки встроке на практике; написать программный код, реализующий один из алгоритмовпоиска подстроки в строке.

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

Конечно, сейчас функциипоиска инкапсулированы во многие языки программирования высокого уровня, поэтомучтобы найти строчку в небольшом тексте используется встроенная функция. Но еслитакого рода поиск является ключевой задачей программы, знать принципыорганизации функций поиска будет полезным. В готовых подпрограммах далеко невсегда все написано лучшим образом. Во-первых, в стандартных функциях не всегдаиспользуются самые эффективные алгоритмы, а во-вторых, вполне возможно, чтопонадобится изменить стандартное поведение этих функций (например,предусмотреть возможность поиска по шаблону). Наконец, область примененияфункции поиска не ограничивается одними лишь текстовыми редакторами. Следуетотметить использование алгоритмов поиска при индексации страниц поисковымроботом, где актуальность информации напрямую зависит от скорости нахожденияключевых слов в тексте html.Работа простейшего спам–фильтра, заключается в нахождении в тексте письма фразтаких, как «Миллион за час» или «Раскрутка сайта». Это всё говорит обактуальности проблемы поиска.

Работа содержит триосновных главы. В первой будут рассмотрены алгоритмы, их теоретическоеобоснование, алгоритмическая модель, будет проведена попытка их классификации.Во второй главе будет рассмотрена практическая часть курсовой работы. Реализованпрограммный код поиска подстроки в строке при помощи алгоритмапоследовательного поиска. В третьей главе работы будут приведены данные опрактическом применении алгоритмов. В заключении будет сделан вывод о наиболееэффективном (с временной точки зрения) алгоритме.

/>/>Глава 1. Теоретические сведения об алгоритмах поискаподстроки в строке 1.1. Основные понятия

Определение. Строка(слово) — это последовательность знаков (называемых буквами) из некоторогоконечного множества, называемого алфавитом.

Определение. Длинастроки – количество знаков в строке.

Слова обозначаютсябуквами латинского алфавита, напр. X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежиталфавиту. Lentgh(X)=/>=n – обозначение длины строки.

Определение. Слово несодержащее ни одной буквы называется пустым.

Пустое слово обычнообозначается буквой L. Length(L)=0.

Определение. Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем самослово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.

Пример: слово ab является префиксом слова abcfa.

Определение. Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично,слово является суффиксом самого себя.

Пример: слово bfg является суффиксом слова vsenfbfg.

Определение. Слово X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называетсялевым, а Z2 — правым крылом подстроки. Подстрокой может быть исамо слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение снаименьшей длиной своего левого крыла называют первым или главным вхождением.Для обозначения вхождения используют обозначение X/>Y.

Пример: слова hrf и fhrявляется подстроками слова abhrfhr,gf/>sfdgfro.

В программированиипонятие сложности алгоритма связано с использованием ресурсов компьютера:насколько много процессорного

времени требует программадля своего выполнения, насколько много при этом расходуется память машины? Учетпамяти обычно ведется по объему данных и не принимается во внимание память,расходуемая для записи команд программы. Время рассчитывается в относительныхединицах так, чтобы эта оценка, по возможности, была одинаковой для машин сразной тактовой частотой.

Существует двехарактеристики сложности алгоритмов — временная и емкостная.

Временная сложность будетподсчитываться в исполняемых командах: количество арифметических операций,количество сравнений, пересылок (в зависимости от алгоритма). Емкостнаясложность будет определяться количеством переменных, элементов массивов,элементов записей или просто количеством байт.

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

 1.2. />Алгоритм последовательного (прямого) поиска

Самый очевидный алгоритм.Обозначеное S — слово, в котором ищется образец X. Пусть m и n — длины слов S иX соответственно. Можно сравнить со словом X все подслова S, которые начинаютсяс позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующаяпозиция. Реализация этого алгоритма представлена в приложении 1.

Это не эффективныйалгоритм т.к. максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство изних на самом деле лишние. Оценим скорость работы этого программного кода. В нейприсутствуют два цикла (один вложенный), время работы внешнего большей степеньюзависит от n, а внутренний в худшем случае делает m операций. Таким образом,время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поискпроработает быстро, но если в каком-то многомегабайтном файле будет искатьсяпоследовательность длинной 100 Кб, то придется ждать ну очень долго. Впрочеммногим хватает и этого. Например, найдя строку aabc и обнаружив несоответствиев четвертом символе (совпало только aab), алгоритм будет продолжать сравниватьстроку, начиная со следующего символа, хотя это однозначно не приведет крезультату.

 1.3. Алгоритм Рабина

Алгоритм Рабинапредставляет собой модификацию линейного алгоритма.

В слове A, длина которогоравна m, ищется образец X длины n. Вырежем «окошечко» размером n оно двигаетсяпо входному слову. Совпадает ли слово в «окошечке» с заданнымобразцом? Фиксируется некоторая числовая функция на словах длины n, тогдазадача сводится к сравнению чисел, что, несомненно, быстрее. Если значения этойфункции на слове в «окошечке» и на образце различны, то совпадениянет. Только если значения одинаковы, необходимо проверять последовательносовпадение по буквам.

Этот алгоритм выполняетлинейный проход по строке (n шагов) и линейный проход по всему тексту (mшагов), стало быть, общее время работы есть O(n+m). При этом не учитываетсявременная сложность вычисления хеш-функции, так как, суть алгоритма в том изаключается, чтобы данная функция была настолько легко вычисляемой, что ееработа не влияла на общую работу алгоритма. Тогда, время работы алгоритмалинейно зависит от размера строки и текста, стало быть программа работаетбыстро. Ведь вместо того, чтобы проверять каждую позицию на предметсоответствия с образцом, можно проверять только те, которые «напоминают»образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будетиспользоваться функция, которая должна:

1. Легко вычисляться.

2. Как можно лучшеразличать несовпадающие строки.

3. hash( y[ i+1, i+m ] ) должна легко вычисляться по hash( y[ i, i+m-1 ].

Во время поиска х будетсравниваться hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно.Если обнаруживается совпадение, то проверяется посимвольно. Реализация этогоалгоритма представлена в приложении 2.

Пример (удобной длявычисления функции). Заменяются все буквы в слове и образце их номерами,представляющими собой целые числа. Тогда удобной функцией является сумма цифр.(При сдвиге «окошечка» нужно добавить новое число и вычесть«пропавшее».)

Однако, проблема в том,что искомая строка может быть длинной, строк в тексте тоже хватает. А так каккаждой строке нужно сопоставить уникальное число, то и чисел должно быть много,а стало быть, числа будут большими (порядка D*n, где D — количество различныхсимволов), и работать с ними будет так же неудобно. Но какой интерес работатьтолько с короткими строками и цифрами? Выше рассмотренный алгоритм можноулучшить.

Пример (семейства удобныхфункций). Выбирается некоторое число p (желательно простое) и некоторый вычет xпо модулю p. Каждое слово длины n будет рассматриваться как последовательностьцелых чисел (заменив буквы их кодами). Эти числа будут рассматриваться каккоэффициенты многочлена степени n-1 и вычисляется значение этого многочлена помодулю p в точке x. Это и будет одна из функций семейства (для каждой пары p иx получается своя функция). Сдвиг «окошечка» на 1 соответствуетвычитанию старшего члена, умножению на x и добавлению свободного члена.Следующее соображение говорит в пользу того, что совпадения не слишкомвероятны. Пусть число p фиксировано и к тому же оно является простым, а X и Y — два различных слова длины n. Тогда им соответствуют различные многочлены (мыпредполагаем, что коды всех букв различны — это возможно при p, большем числабукв алфавита). Совпадение значений функции означает, что в точке x эти дваразличных многочлена совпадают, т.е. их разность обращается в 0. Разность естьмногочлен степени n-1 и имеет не более n-1 корней. Таким образом, если n многоменьше p, то случайному значению x мало шансов попасть в «неудачную»точку.

Строго говоря, времяработы всего алгоритма в целом, есть O(m+n+mn/P), mn/P достаточно невелико, такчто сложность работы почти линейная. Понятно, что простое число следуетвыбирать большим, чем больше это число, тем быстрее будет работать программа.

Алгоритм Рабина иалгоритм последовательного поиска являются алгоритмами с наименьшимитрудозатратами, поэтому они годятся для использования при решении некоторогокласса задач. Однако эти алгоритмы не являются наиболее оптимальными (хотя быпотому, что иногда выполняют явно бесполезную работу, о чем было сказано выше),поэтому будет рассматриваться следующий класс алгоритмов. Эти алгоритмыпоявились в результате тщательного исследования алгоритма последовательногопоиска. Исследователи хотели найти способы более полно использовать информацию,полученную во время сканирования (алгоритм прямого поиска ее простовыбрасывает).

 1.4.Алгоритм Кнута — Морриса — Пратта (КМП)

Метод используетпредобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция.Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшейподстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в концеподстроки (как префикс и как суффикс). Например, для подстроки abcHelloabcтакой подстрокой является abc (одновременно и префиксом, и суффиксом). Смыслпрефикс-функции в том, что можно отбросить заведомо неверные варианты, т.е.если при поиске совпала подстрока abcHelloabc (следующий символ не совпал), тоимеет смысл продолжать проверку продолжить поиск уже с четвертого символа(первые три и так совпадут). Вначале рассматриваются некоторые вспомогательныеутверждения. Для произвольного слова X рассматриваются все его начала,одновременно являющиеся его концами, и выбираются из них самое длинное (несчитая, конечно, самого слова X). Оно обозначается n(X). Такая функция носитназвание префикс – функции [13].

Примеры.

n(aba)=a,n(n(aba))=n(a)=L;

n(abab)=ab,n(n(abab))=n(ab)=L;

n(ababa)=aba,n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=L; n(abc)=L.

Справедливо следующеепредложение:

 (1) Последовательностьслов n(X),n(n(X)),n(n(n(X))),… «обрывается» (на пустом слове L).

(2) Все словаn(X),n(n(X)),n(n(n(X))),...,L являются началами слова X.

(3) Любое слово,одновременно являющееся началом и концом слова X (кроме самого X), входит впоследовательность n(X),n(n(X)),....,L.

Метод КМП используетпредобработку искомой строки, а именно: на ее основе создается префикс-функция.При этом используется следующая идея: если префикс (он же суффикс) строкидлинной i длиннее одного символа, то он одновременно и префикс подстрокидлинной i-1. Таким образом, проверяется префикс предыдущей подстроки, если жетот не подходит, то префикс ее префикса, и т.д. Действуя так, находитсянаибольший искомый префикс. (см. приложение 3).

Следующий вопрос, накоторый стоит ответить: почему время работы процедуры линейно, ведь в нейприсутствует вложенный цикл? Ну, во-первых, присвоение префикс-функциипроисходит четко m раз, остальное время меняется переменная k. Так как в циклеwhile она уменьшается (P[k]<k), но не становится меньше 0, то уменьшатьсяона может не чаще, чем возрастать. Переменная k возрастает на 1 не более m раз.Значит, переменная k меняется всего не более 2m раз. Выходит, что время работывсей процедуры есть O(m).

Алгоритмпоследовательного поиска и алгоритм КМП помимо нахождения самих строк считают,сколько символов совпало в процессе работы. Реализация этого алгоритмапредставлена в приложении 4.

1.5.Алгоритм Бойера – Мура

Алгоритм Бойера-Мура,разработанный двумя учеными – Бойером и Муром, считается наиболее быстрым средиалгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Простейший варианталгоритма Бойера-Мура состоит из следующих шагов. На первом шаге строитсятаблица смещений для искомого образца. Процесс построения таблицы будет описанниже. Далее совмещается начало строки и образца и начинается проверка с последнегосимвола образца. Если последний символ образца и соответствующий ему приналожении символ строки не совпадают, образец сдвигается относительно строки навеличину, полученную из таблицы смещений, и снова проводится сравнение, начинаяс последнего символа образца. Если же символы совпадают, производится сравнениепредпоследнего символа образца и т. д. Если все символы образца совпали сналоженными символами строки, значит нашлась подстрока и поиск окончен. Если жекакой-то (не последний) символ образца не совпадает с соответствующим символомстроки, сдвигается образец на один символ вправо и снова начинается проверку споследнего символа. Весь алгоритм выполняется до тех пор, пока либо не будетнайдено вхождение искомого образца, либо не будет достигнут конец строки.

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

Величина смещения длякаждого символа образца зависит только от порядка символов в образце, поэтомусмещения удобно вычислить заранее и хранить в виде одномерного массива, гдекаждому символу алфавита соответствует смещение относительно последнего символаобразца.

Пример. Пусть естьалфавит из пяти символов: a, b, c, d, e и надо найти вхождение образца “abbad”в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполненияалгоритма. Таблица смещений будет выглядеть так.

/>

Начало поиска.

/>

Последний символ образцане совпадает с наложенным символом строки. Сдвигается образец вправо на 5позиций:

/>

Три символа образцасовпали, а четвертый – нет. Сдвигается образец вправо на одну позицию:

/>

Последний символ снова несовпадает с символом строки. В соответствии с таблицей смещений сдвигаетсяобразец на 2 позиции:

/>

Еще раз сдвигаетсяобразец на 2 позиции:

/>

Теперь, в соответствии стаблицей, сдвигается образец на одну позицию, и получается искомое вхождениеобразца:

/>

Прежде всего следуетопределить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256символов, определение этого типа будет выглядеть так:

Type

TBMTable =Array [0..255] of Integer;

Реализация процедуры,вычисляющая таблицу смещений для образца p, представлена в приложении 5.

Теперь пишется функция,осуществляющая поиск (см. Приложение 6).

Параметр StartPosпозволяет указать позицию в строке s, с которой следует начинать поиск. Этоможет быть полезно в том случае, если надо найти все вхождения p в s. Дляпоиска с самого начала строки следует задать StartPos равным 1. Если результатпоиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужнозадать StartPos равным значению «предыдущий результат плюс длина образца».

Глава2. Практическая часть.Дан некоторый текст, в котором следуетнайти фрагмент этого текста.

Данную задачу можноинтерпретировать как поиск подстроки в строке.

Эту задачу я реализовалпри помощи алгоритма последовательного (прямого) поиска. Программный код задачиреализовал на языке программирования Turbo Pascal 7.1 и он представленв приложении 7.

Описание работыпрограммы.

После запуска программазапрашивает ввод текста:

Например, введём следующийтекст: ”алгоритм рабина представляет собой модификацию линейного алгоритма.”

/>

Далее программазапрашивает ввод строки(подстроки) для поиска:

Например, вводим фрагменттекста: ”алгоритм”

/>

После ввода, программаищет строку в тексте, если строка существует то программа выводит текст наэкран, выделяет строку красным цветом и выдает с какого символа начинаетсястрока:

/>

Если фрагмента нет втексте, то программа выдаст сообщение о том, что данной строки в тексте несуществует:

/>

Глава 3. Анализ алгоритмов

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

Задача: Имеется несколькотекстовых файлов, содержащих 10000 записей вида:

—   строка

—   подстрока(имеющаяся в данной строке)

—   место вхождения

—   длина подстроки,

причем с разнымимаксимальными длинами строк и подстрок.

Алфавит кириллицысодержит 32 буквы, поэтому длина строки будет не более 10, 100, 250 символов.

Проводится поиск подстрокв строках для каждого из алгоритмов и измеряется время работы программы. Приэтом будет учитываться следующее:

·         строкипредварительно загружаем в оперативную память (в виде массива), причем времясчитывания в массив не учитывается. Предобработка (создание таблиц перехода)входит в общее время.

·         каждый алгоритмзапускается 5 раз, время выбирается наименьшее.

Эксперимент проходил наПК:

Процессор Intel Pentium IV 2,66Ггц

1024 Мб ОЗУ

Компилятор Turbo Pascal 7.1

Фрагмент кода тестируемойпрограммы приводится в Приложении 8.

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

Эксперимент проводилсядля четырех алгоритмов – представителей классов алгоритмов. Так как всеалгоритмы ставились в одинаковые условия, то можно провести их сравнительныйанализ. Заметим, что данный анализ применим только для данных параметровпоиска, и при иных условиях может отличаться.

Таблица 1

  Результаты экспериментазанесены в таблицу 1.Алгоритм Время выполнения (мс) Длина ≤10 Длина ≤100 Длина ≤250 Послед. Поиск 15 93 234 Алгоритм Рабина 15 63 93 КМП 5 30 50 БМ 31 31 32

Изтаблицы видно, что алгоритм Бойера – Мура справился с экспериментальной задачейбыстрее остальных. Следует, однако, заметить, что его эффективность растет лишьс увеличением длины строки и, соответственно, длины образца. Так при длинестроки меньшей или равной 10 символов, он показал себя хуже, чем последовательныйпоиск. Аналогичные результаты показывает и алгоритм КМП, как для коротких, таки для длинных слов. Его можно использовать как универсальный, когда неизвестныдлины строки и образца.

Алгоритм Рабина, при егосхожести с последовательным работает быстрее, а его простота и малыетрудозатраты на реализацию, делают его привлекательным для использования внеспециальных программах.

Наихудший результатпоказал алгоритм последовательного поиска. Как предполагалось лишь принебольшом увеличении длины строки, он работает существенно медленнее остальныхалгоритмов.

Заключение

В процессе выполнениякурсовой работы были рассмотрены различные алгоритмы поиска подстроки в строкеи проведен их сравнительный анализ, результаты которого представлены в таблице2 (см. приложение 9).

Изучив полученныерезультаты легко можно сделать вывод, что алгоритм Бойера – Мура являетсяведущим по всем параметрам. Но, как показывает эксперимент, алгоритм Кнута –Мориса — Пратта, превосходит алгоритм БМ на небольших длинах образца. Поэтому нельзясделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждыйалгоритм эффективно работает в определенных классах задач, об этом еще говорятразличные узконаправленные улучшения каждого из алгоритмов. Таким образом, типалгоритмов поиска подстроки в строке следует выбирать только после точнойпостановки задачи, определение её целей и функциональности, которая она должнареализовать.

Только после этого этапанеобходимо переходить к реализации программного кода.

В связи с глобализациейинформации в сети internet былразработан интеллектуальный поиск. Который позволяет найти документ по смыслу содержащейся в нем информации, тоесть документы по заданной теме. В системе реализован алгоритм с использованиемкомпьютерной обработки документа. Согласно гипотезе Ципфа смысл документазависит от частоты терминов, встречающихся в документе. Однако гораздо важнеене сама частота слова, а то, насколько часто в текущем документе это слововстречается относительно других слов.

Список используемой литературы:

1) Альсведе Р., Вегенер И.«Задачи поиска», 1982г, Издательство «Мир»

2). Ахо, Альфред Структура данных иалгоритмы [Текст]. – М.: Издательский дом «Вильямс», 2000. — 384 с.

3). Белоусов А. Дискретная математика[Текст]. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001. – 744 с.

4). Брайан, К. Практикапрограммирования [Текст].- СПб:. Невский диалект, 2001. — 381 с.

5). Вирт, Н. Алгоритмы и структурыданных [Текст].– М:. Мир, 1989. – 360 с.

6) Кнут, Д. Искусствопрограммирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с.

7). Кормен, Т. Алгоритмы: построениеи анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест — М.: МЦНМО, 2002. М.:МЦНМО, 2002.

8). Успенский В. Теория алгоритмов:основные открытия и приложения [Текст]. – М.: Наука, 1987. – 288 с.

9). Шень, А. Программирование:теоремы и задачи [Текст]. – М.: Московский центр непрерывного математическогообразования, 1995.

Электронныеисточники.

1) www.ipkro.isu.ru/informat/methods/findsort/

2) www.delphikingdom.com/asp/viewitem.asp?catalogid=65

3) revolution./programming/00013926_0.html

4) ric.uni-altai.ru/fundamental/pascal1/lab15/l15-teor.htm

5) www.rsdn.ru/article/alg/textsearch.xml

Приложение1

 

Реализацияалгоритма последовательного поиска

Function Search (S: String; X: String; var Place: Byte): Boolean;

{ Функция возвращает результат поиска в слове S }

{ подслова X. Place — место первого вхождения }

var Res: Boolean; i: Integer;

Begin

Res:=FALSE;

i:=1;

While (i<=Length(S)-Length(X)+1) And Not(Res) do

If Copy(S,i,Length(X))=X then

begin

Res:=TRUE;

Place:=i

end

else i:=i+1;

Search:=Res

End;

  />

Приложение2

 

Реализацияалгоритма Рабина

Function Search (S: String; X: String; var Place: Byte): Boolean;

{ Функция возвращает результат поиска в слове S }

{ подслова X. Place — место первого вхождения }

Var Res: Boolean; i: Byte; h,NowH,LenX:Integer; HowMany:Integer;

Begin

Res:=FALSE;

i:=1;

h:=Hash(x); {Вычисление хеш-функции для искомого слова}

NowH:=Hash(Copy(S,1,Length(x)));

HowMany:=Length(S)-Length(X)+1;

LenX:=Length(X);

While (i<=HowMany) And Not(Res) do

If (h=NowH) and (Copy(S,i,Length(X))=X) then

Begin

Res:=TRUE;

Place:=i

End

else

Begin

i:=i+1;

NextHash(s,i,NowH,LenX); {Вычисление следующего значения хеш-функции}

End;

Search:=Res

End;

  />
Приложение 3 Алгоритм Кнута-Морриса-Пратта

Нахождение наибольшегоискомого префикса.

Procedure PrefFunc(P:String; Var Fl:TMas);

Var n,i,j:Integer;

Begin

n:=Length(P);

Fl[1]:=0;

For i:=2 To n Do

Begin

j:=Fl[i-1];

While (j<>0) And (P[j]<>P[i-1]) Do j:= Fl[j];

Fl[i]:=j+1;

End;

End;

  />

Приложение4

 Реализация алгоритмаКнута-Морриса-Пратта

Function KMPSearch(S,P:String):Integer;

{ Алгоpитм Кнута-Моpиса-Пpатта, устанавливающий }

{ вхождение непустой стpоки P в стpоку S }

Var Fl:TMas;

i,j,n,m:Integer;

Begin

n:=Length(S);

m:=Length(P);

PrefFunc(P,Fl);

j:=1;

For i:=1 To n Do

begin

While (j<>0) And (P[j]<>S[i]) do j:=Fl[j];

If j=m Then Break;

j:=j+1

end;

If (j=m) then Result:=i-j+1 Else Result:=0;

End;

  />

Приложение5

 Алгоритм Бойера-Мура Реализация процедуры, вычисляющая таблицусмещений для образца p.

Procedure MakeMBTable( var Bmt: TBMTable; Const p: string);

Var   i: Integer;

Begin

  For i := 0 to 255 do Bmt[i] := Length(p);

    For i := Length(p) Downto 1 Do

      If  Bmt[Byte(p[i])] = Length(p) Then

        Bmt[Byte(p[i])] := Length(p) – i;

End;

  />

Приложение6

 Алгоритм Бойера-Мура

Функция, осуществляющаяпоиск.

function bmsearch( startpos: integer; const s, p: string;

  const bmt: tbmtable: integer;)

var

  pos, lp, i: integer;

begin

  lp := length(p);

  pos := startpos + lp –1;

  while pos < length(s) do

    if p[lp] <> s[pos] then pos := pos + bmt[s[pos]]

    else for i := lp — 1 downto 1 do

      if p[i] <> s[pos – lp + i] then

      begin

        inc(pos);

        break;

      end

      else if i = 1 then

      begin

        result := pos – lp + 1;

        exit;

      end; 

  result := 0;

end;

  />

Приложение7

 Реализация программного кода

program Poisk;

        uses crt;

         var

         t,s,tex,t2:string; p,i,d1,d2,d3,x:integer; text:array [1..100] of string;

begin

     clrscr;  { }

     textcolor(10);

     writeln('Введите текст');

     textcolor(15);

     readln(t);                

      writeln;

     textcolor(10);

     writeln(‘Введите строку’);

     textcolor(15);

     readln(s);                

      writeln;

      d3:=0;

        repeat

               textcolor(10);

               p:=pos(s,t);    

               if p=0 then

               if x>1 then

                begin

                writeln;

               writeln('Конец поиска. Для выхода нажмите Enter.')

               end

               else

            writeln('Такой строки в тексте не существует. Для выхода нажмите Enter.') 

               else

begin

              tex:=tex+text[x];

              d3:=length(tex);

               writeln;

              writeln('Образец входит в текст с  ',p+d3,'-ого символа ');

                writeln;

             d1:=length(s);

           textcolor(15);

           write(tex);

           for i:=1 to p-1 do

           write(t[i]);

                for i:=1 to d1 do

                begin

                    textcolor(12);

                    write(s[i]);

                end;

  /> 
/> <td/>

d2:=length(t);

                       for i:= d1+p to d2 do

                         begin

                           textcolor(15);

                           write(t[i]);

                         end;

                    readln;

                 x:=x+1;

                 text[x]:=copy(t,1,p+d1-1);

                 delete(t,1,p+d1-1);

          end;

         until p=0;

     readln;

end.

 
Приложение 8

 

Фрагменткода тестируемой программы

 

  LoadFromFile('C:\String_250.txt');

{Происходит загрузка в массив}

  Tick:=GetTickCount;

{Запоминаем текцщее значение переменной Tick}

  Poisk;

 {Процедура в которой происходит поиск 10000 раз}

  Tick:=GetTickCount-Tick;

{Получаем разницу – время в миллисекундах}

  WriteLn('Za vremja ',Tick, ' ms');

  />

Приложение9

Общиерезультаты с анализов рассмотренных алгоритмов

/> <td/>

Таблица 2

 
Примечания Алгоритмы, основанные на алгоритме последовательного поиска Малые трудозатраты на программу, малая эффективность Алгоритм Кнута-Морриса-Пратта Универсальный алгоритм, если неизвестна длина образца Алгоритм Бойера-Мура Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. Время работы (мс) при длине строки ≤250 234 93 31 32 Затраты памяти нет нет O(m) O(m+s) Худшее время поиска O((m-n+1)*n+1) O((m-n+1)*n+1) O(n+m) O(n*m) Среднее время поиска O((m-n+1)*n+1)/2 O(n+m) O(n+m) O(n+m) Время на пред. обработку нет нет O(m) O(m+s) Алгоритм Алгоритм прямого поиска Алгоритм Рабина КМП БМ