Поиск подстроки в строке

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского»

Кафедра математической кибернетики и компьютерных наук

КУРСОВАЯ РАБОТА

Поиск подстроки в строке

Саратов, 2011

Введение

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

В настоящее время функции поиска подстроки в строке инкапсулированы во многие высокоуровневые языки программирования. Но стоит помнить, что стандартные функции далеко не самые оптимальные и эффективные, и если основной задачей программы является нахождение подстроки в строке, то необходимо знать принципы организации функций поиска. Также не нужно забывать, что область применения функций поиска не ограничивается одними текстовыми редакторами и базами данных. Алгоритмы поиска используются различными поисковыми роботами при индексации страниц, и от скорости нахождения необходимых ключевых слов в тексте html зависит актуальность информации. Спам-фильтр почтовых сервисов также занимается поиском в тексте писем определенных фраз, например: «Миллион за час», «Голосуй за Иванова!». Да даже фильтр нецензурных слов и выражений в MMORPG (massively multiplayer online role-playing game - многопользовательская ролевая онлайн-игра) является примером применения данной задачи. Все это говорит об актуальности проблемы поиска подстроки в строке.

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

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

1. Алгоритмы поиска подстроки в строке

1.1 Основные определения и понятия

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

Определение [1]. Длина строки - количество знаков в строке.

Слова обозначаются буквами латинского алфавита, например последовательность - слово длинной , где -ая буква слова. Будем обозначать длину строки .

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

Определение [1]. Слово называется префиксом слова , если есть такое слово , что . Причем само слово является префиксом для самого себя, так как найдется нулевое слово , что .

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

Определение [1]. Слово называется суффиксом слова , если есть такое слово , что . Аналогично, слово является суффиксом самого себя.

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

Определение [1]. Слово называется подстрокой строки , если найдутся такие строки и , что . При этом называется левым, а - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово называют вхождением в слово . Среди всех вхождений слова в слово , вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение .

Пример: слова asd и qwe являются подстроками слова ryrqwetrasdyrt.

Определение [5]. Сложность алгоритма - зависимость объема работы, выполняемой алгоритмом от размера входных данных. Причем, объем работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Т.е. сложность алгоритма - это количество времени, необходимое для выполнения алгоритма, и объем расходующейся при этом памяти. Учет памяти обычно ведется по объему данных. Время же рассчитывается в относительных единицах так, чтобы эта оценка была одинаковой для процессоров с разной частотой.

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

Временная сложность подсчитывается в исполняемых процессором командах: количество арифметических операций, сравнений и ссылок.

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

Эффективность алгоритма оценивается с помощью подсчета времени, затраченного программой для выполнения конкретной задачи в ходе эксперимента [5].

1.2 Простейшие алгоритмы поиска подстроки в строке

1.2.1 Алгоритм последовательного поиска

Алгоритм последовательного поиска - самый очевидный алгоритм. Пусть - строка, в которой выполняется поиск, а - искомое слово, и . Тогда для поиска подстроки (слова) в строке можно выполнить сравнение каждой подстроки , начинающейся с позиций , длиной . И при совпадении вывести соответствующий номер первого элемента найденной подстроки [5].

Стоит сказать, что это самый неоптимальный и неэффективный алгоритм.

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

1.2.2 Алгоритм Рабина-Карпа

Алгоритм Рабина-Карпа представляет собой модифицированную версию алгоритма последовательного поиска. Его отличительной чертой является применение хеширования - преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины [5].

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

Этот алгоритм выполняет линейный проход по искомому фрагменту ( шагов) и линейный проход по всему тексту ( шагов), стало быть, общее время работы есть . Здесь не учитывается время на вычисление хеш-функции. Потому что сама идея алгоритма построена на условии, что хеш-функция будет легко вычисляться, и время этого вычисления не будет влиять на работу алгоритма. Примером такой легко вычисляемой хеш-функции может быть функция, которая считает сумму кодов символов слова в «окошечке». Таким образом, при сдвиге «окошечка» на один элемент вправо не нужно заново считать всю сумму. Достаточно просто вычесть код первого символа до сдвига и добавить код нового символа, попавшего в диапазон. Совпадение подсчитанного значения суммы со значением хеш-функции искомого слова при их посимвольном несоответствии не слишком вероятно, однако, в худшем случае время работы будет . Широкое распространение алгоритм Рабина не получил, однако, он часто используется в программах поиска плагиата [2].

1.3 Эффективные алгоритмы поиска подстроки в строке

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

Однако эти алгоритмы используют чуть больше трудозатрат и имеют время предварительной обработки. Но операций сравнения становится в разы меньше, и мы можем говорить о линейной зависимости этих алгоритмов от величины строки . [5]

1.3.1 Алгоритм Кнута-Морриса-Пратта

Данный алгоритм был предложен в 1977 году учеными Кнутом, Праттом и независимо от них Моррисом. Предложенный ими метод выполняет предварительную обработку искомой строки. На её основе создается префикс-функция, которая инкапсулирует сведения о том, в какой мере образец совпадает сам с собой после сдвигов. Т.е. префиксной функцией заданного образца называется функция , такая что

. (1)

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

Рис.1. Иллюстрация для образца P = ababababca и q = 8.

Смысл префикс-функции в том, что можно отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcasdqtabc (следующий символ не совпал), то имеет смысл продолжать проверку уже с четвертого символа (первые три и так совпадут). Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной больше одного символа, то он одновременно и префикс подстроки длинной . Таким образом, проверяется префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находится наибольший искомый префикс [4, 5, 7].

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

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

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

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

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

Приведем пример работы алгоритма. Пусть существует алфавит из пяти символов: q, w, e, r, t и необходимо найти вхождение образца “qwwqr” в строке “qwteeqewqrwqwwqr”. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так.

q	w	e	r	t
1	2	5	0	5

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

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

Так как последний символ искомой строки не совпадает с соответствующим символом исходной строки, то образец смещается вправо на величину из таблицы смещений, соответствующую символу «e» - на 5 позиций.

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

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

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

Снова не совпадает последний символ искомой строки, выполняется сдвиг на 2 позиции вправо.

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

Ещё раз выполняется сдвиг вправо на 2 позиции.

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

В соответствии со значением смещения для символа q выполняется сдвиг на 1 позицию.

q

w

t

e

e

q

e

w

q

r

w

q

w

w

q

r

q

w

w

q

r

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

подстрока строка алгоритм программа

2. Реализация алгоритмов

В курсовой работе были реализованы четыре алгоритма поиска подстроки в строке. Листинг программного кода алгоритма последовательного поиска представлен в Приложении А, алгоритма Рабина-Карпа в Приложении Б, алгоритма Кнута-Морриса-Пратта в Приложении В и алгоритма Бойера-Мура в приложении Г.

Тестирование алгоритмов проводилось на ПК:

Процессор Intel® Atom™ CPU N455 с тактовой частотой 1.66 ГГц

1024 Мб ОЗУ

Компилятор Microsoft Visual Studio 2008.

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

2.1 Описание программы

Программа разработана как проект WindowsFormApplication на языке программирования C# в среде разработки Microsoft Visual Studio 2008.

Пусть дан некоторый текстовый файл, в котором необходимо найти все вхождения какого-либо фрагмента. Данную задачу можно интерпретировать как поиск подстроки в строке. Пользователю предлагается на выбор четыре алгоритма поиска: алгоритм последовательного поиска, алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта и алгоритм Бойера-Мура.

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

2.2 Порядок работы с приложением

После запуска приложения открывается основное окно программы (рис. 2.1), в котором можем наблюдать несколько элементов:

кнопка «Выбрать файл поиска»;

кнопка «Выполнить поиск»;

четыре кнопки выбора алгоритмов;

поле, для ввода искомого фрагмента.

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

Рис. 2.1. Основное окно программы

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

Рис. 2.2. Диалоговое окно

Далее необходимо ввести искомый фрагмент в соответствующее поле и выбрать алгоритм поиска. Введем в окно текст: «Уважаемые граждане России!» и выберем алгоритм поиска Бойера-Мура (рис. 2.3).

Рис. 2.3. Выбор алгоритма

После нажатия на кнопку «Выполнить поиск» поочередно появляются два окна «Количество тактов процессора» (рис. 2.4) и «Результат поиска» (рис.2.5).

Рис. 2.4. Количество тактов процессора

Рис. 2.5. Результат поиска

Также открывается файл, в котором был произведен поиск (рис. 2.6).

Рис. 2.6. Текстовый файл «Выступление Путина.txt»

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

Рис. 2.7. Неудачный поиск

3. Тестирование алгоритмов

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

Было составлено случайным образом 10 раз три текстовых файла из строчных букв латинского алфавита, длиной в 1000, 10000 и 100000 символов. В каждом из этих файлов выполнялся поиск подстроки, полученной алгоритмом, состоящем из следующих шагов:

Вычисление случайной длины подстроки

Для текстового файла, длиной 1000 символов вычислялась случайная длина искомой подстроки от 10 до 50 символов; для текстового файла, длиной 10000 символов случайная длина подстроки от 100 до 500 символов; и для файла, длиной 100000 символов случайная длина фрагмента вычислялась из диапазона от 1000 до 5000 символов;

Вычисление случайной позиции начала искомой подстроки в файле

Для каждого текстового файла получали случайную позицию подстроки из диапазона от 0 до S.Length-X.Length, где S.Length - длина текстового файла и X.Length - длина искомой подстроки.

Каждый алгоритм выполнял поиск одной и той же подстроки по 10 раз. И в итоге выбирался наилучший результат среди всех попыток.

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

Среднестатистические результаты экспериментов приведены в Таблице 1 и проиллюстрированы на рис. 3. Полный отчет обо всех экспериментах представлен в Таблице 2, в Приложении Е.

Таблица 1. Среднестатистические результаты тестирования алгоритмов поиска

Алгоритм поиска	Время работы алгоритма, такты процессора
	1000 символов	10 тыс. символов	100 тыс. символов
Последовательный	1687	9953	101303
Рабина-Карпа	1718	10524	100300
Кнута-Морриса-Пратта	1647	9710	92453
Бойера-Мура	1414	5803	48262

Рис. 3. Результаты тестирования алгоритмов.

Из Таблицы 2 видно, что алгоритм Бойера-Мура справился с экспериментальной задачей быстрее остальных. Однако его эффективность растет с увеличением длины исходной строки и искомой подстроки. Поэтому на входном файле с 1000 символами он показал результат не много лучше остальных алгоритмов.

Алгоритм Кнута-Морриса-Пратта выполнил задачу быстрее Рабина-Карпа и Последовательного поиска, однако существенно уступил Бойеру-Муру. Но к плюсу этого алгоритма можно отнести относительно небольшой разброс времени работы, независимо от входных данных. Что нельзя сказать об алгоритме Бойера-Мура.

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

Заключение

В курсовой работе были рассмотрены основные алгоритмы поиска подстроки в строке и проведен их сравнительный анализ.

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

Список использованных источников

1. Ахо А. Алгоритмы поиска подстроки в строке // Структура данных и алгоритмы. - М.: «Вильямс», 2000. - С. 384.

2. Брайан К. Практика программирования. - СПб: «Невский диалект», 2001. - С. 381.

3. Вирт Н. Алгоритмы и структуры данных. - М.: «Мир», 1989. - С. 360.

4. Кнут Д. Алгоритм Кнута-Морриса-Пратта // Искусство программирования на ЭВМ. - М.: «Мир», 1978. - т.3. - С. 356.

5. Кормен Т., Лейзерсон И., Ривест Л., Штайн. Алгоритмы поиска подстроки // Алгоритмы: построение и анализ - 2-e издание. - М.: «Вильямс», 2005. - С. 1019 - 1058.

6. Алгоритмы поиска подстроки в строке // «MyKod» [Эл. ресурс]. URL: http://www.mykod.ru/

7. Алгоритм Кнута-Морриса-Пратта // «Maximal» [Эл. ресурс]. URL: http://e-maxx.ru/algo/prefix_function

8. Алгоритм Бойера-Мура // «Исходники» [Эл. ресурс]. URL: http://easylab.net.ua/poisk/algoritm-boyera-mura

Приложение

Приложение А

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

//Функция последовательного поиска

public static string Posl(string x, string s)

{

//Объявление строки с номерами позиций

string nom = "";

//Если искомая строка больше исходной - возврат пустого поиска

if (x.Length > s.Length) return nom;

//Цикл по исходной строке

for (int i = 0; i < s.Length - x.Length+1; i++)

{

bool flag = true; //Флаг

int j = 0;

while ((flag == true) && (j < x.Length))

{

if (x[j] != s[i + j]) flag = false;

j++;

}

//Если искомая строка совпала с частью исходной

if (flag == true)

//Добавление номера позиции в строку номеров

nom = nom + Convert.ToString(i) + ", ";

}

//Если вхождение найдено

if (nom != "")

{

//Удаление последней запятой и пробела

nom = nom.Substring(0, nom.Length - 2);

}

//Возвращение результата поиска

return nom;

}

Приложение Б

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

//Хеш-функция для алгоритма Рабина-Карпа

public static int Hash(string s)

{

int rez = 0;

for (int i = 0; i < s.Length; i++)

{

rez += (int)(s[i]);//Сложение кодов букв

}

return rez;

}

//Функция поиска алгоритмом Рабина

public static string Rabina(string x, string s)

{

string nom = "";

//Если искомая строка больше исходной - возврат пустого поиска

if (x.Length > s.Length) return nom;

//Вычисление хеш-функции искомой строки

int xhash = Hash(x);

//Вычисление хеш-функции первого слова длины образца в строке S

int shash = Hash(s.Substring(0,x.Length));

for (int i = 0; i < s.Length - x.Length; i++)

{

//Если значения хеш-функций совпадают

if (xhash == shash)

{

bool flag = true; //Флаг

int j = 0;

while ((flag == true) && (j < x.Length))

{

if (x[j] != s[i + j]) flag = false;

j++;

}

//Если искомая строка совпала с частью исходной

if (flag == true)

nom = nom + Convert.ToString(i) + ", ";

}

//Иначе вычисление нового значения после сдвига

else shash = shash - (int) (s[i]) +

(int)(s[i + x.Length]);

}

//Если вхождение найдено

if (nom != "")

{

nom = nom.Substring(0, nom.Length - 2);

}

return nom;

}

Приложение В

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

//Префикс-функция для КМП

public static int[] PrefFunc(string x)

{

//Инициализация массива-результата длиной X

int[] res = new int[x.Length];

int i = 0;

int j = -1;

res[0] = -1;

//Вычисление префикс-функции

while (i < x.Length - 1)

{

while ((j >= 0) && (x[j] != x[i]))

j = res[j];

i++;

j++;

if (x[i] == x[j])

res[i] = res[j];

else

res[i] = j;

}

return res;//Возвращение префикс-функции

}

//Функция поиска алгоритмом КМП

public static string KMP(string x, string s)

{

//Объявление строки с номерами позиций

string nom = "";

if (x.Length > s.Length) return nom;

//Вызов префикс-функции

int[] d = PrefFunc(x);

int i=0, j;

while (i < s.Length)

{

for (i = i, j = 0; (i < s.Length) &&

(j < x.Length); i++, j++)

while ((j >= 0) && (x[j] != s[i]))

j = d[j];

if (j == x.Length)

nom = nom + Convert.ToString(i - j) + ", ";

}

if (nom != "")

{

//Удаление последней запятой и пробела

nom = nom.Substring(0, nom.Length - 2);

}

return nom;

}

Приложение Г

Реализация алгоритма Бойера-Мура

//Таблица символов искомой строки

public static char[] SymbolOfX;

//Таблица смещений для символов

public static int[] ValueShift;

//Процедура - формирование смещений

public static void ShiftBM(string x)

{

int j;//Счетчик

int k = 0;//Счетчик

bool fl;//Флаг

SymbolOfX = new char[x.Length];//Инициализация

ValueShift = new int[x.Length];//Инициализация

//Цикл по искомой строке без последнего символа

for (int i = x.Length-2; i >= 0; i--)

{

fl = false;//Флаг

j = 0;//Обнуление

while ((j<k+1)&&(fl == false))

{

if (SymbolOfX[j] == x[i]) fl = true;

j++;

}

if (fl == false)

{

SymbolOfX[k] = x[i];

ValueShift[k] = x.Length - i - 1;

k++;

}

}

}

//Функция поиска алгоритмом БМ

public static string BM(string x, string s)

{

bool has, have;//Флаги

int l,j,i;//Счетчики

//Вызов процедуры, формирубщей таблицу смещений

Function.ShiftBM(x);

//Объявление строки с номерами позиций

string nom = "";

if (x.Length > s.Length) return nom;

//Основной цикл по исходной строке

for (i = 0; i < s.Length-x.Length+1; i++)

{

j = x.Length - 1;

have = true;

//Проверка с последнего символа

while ((j >= 0)&&(have == true))

{

//Если не совпадает символ искомой и исходной

if (s[i + j] != x[j])

{

have = false;

//Если это последний символ

if (j == x.Length-1)

{

l = 0;

has = false; //Флаг

//Поиск символа в таблице смещений

while ((l < x.Length)&&(has == false))

{

//Если символ есть

if (s[i + j] == SymbolOfX[l])

{

has = true; //Изменение флага

//Сдвиг на величину

i = i + ValueShift[l] - 1;

}

l++;

}

//Если не найден символ в таблице смещений

if (has == false)

//Сдвиг на величину искомой строки

i = i + x.Length - 1;

}

}

j--;

}

if (have == true)

nom = nom + Convert.ToString(i) + ", ";

}

//Если строка номеров не пустая

if (nom != "")

{

//Удаление последней запятой и пробела

nom = nom.Substring(0, nom.Length - 2);

}

return nom;//Возвращение результата поиска

}

Приложение Д

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

Код формы:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

using Fuction;

using System.Diagnostics;

using System.Threading;

namespace KurgachevND_Kursovaya_1kurs

{

public partial class Form1 : Form

{

public static string str,//Объявление исходной строки

nom;//Объявление строки с результатами поиска

public Form1()

{

InitializeComponent();

//Отключение кнопки: "Выполнить поиск"

button3.Enabled = false;

//Отключение кнопок выбора алгоритма

radioButton1.Enabled = false;

radioButton2.Enabled = false;

radioButton3.Enabled = false;

radioButton4.Enabled = false;

label2.Text = "";

}

//Событие - клик на кнопку «Выбрать файл поиска»

private void button1_Click(object sender, EventArgs e)

{

//Очистка исходной строки

str = "";

//Фильтр открываемых файлов

openFileDialog1.Filter = "Text files (*.TXT)|*.txt";

//Очистка имени открываемого файла

openFileDialog1.FileName = "";

//Если файл выбран

if (openFileDialog1.ShowDialog() == DialogResult.OK)

{

FileStream TextFile = new FileStream(openFileDialog1.FileName, FileMode.Open);

//Запись имени открываемого файла в элемент формы

label2.Text = openFileDialog1.SafeFileName.Substring(0, openFileDialog1.SafeFileName.Length - 4);

//Закрытие потока данных

TextFile.Close();

using (StreamReader sr = new StreamReader(openFileDialog1.FileName,Encoding.Default))

{

//Считывание текста в строку

str = sr.ReadToEnd();

}

//Включение кнопок выбора алгоритмов

radioButton1.Enabled = true;

radioButton2.Enabled = true;

radioButton3.Enabled = true;

radioButton4.Enabled = true;

}

}

//Событие - клик на кнопку «Выполнить поиск»

private void button3_Click(object sender, EventArgs e)

{

//Если окно искомого фрагмента пустое - сообщение об ошибке

if (textBox1.Text == "")

MessageBox.Show("Отсутствует искомый фрагмент","Ошибка");

//Выполнение поиска искомого фрагмента

else

{

//Если выбран последовательный поиск

if (radioButton1.Checked == true)

{

Stopwatch stopWatch = new Stopwatch();

//Старт счетчика тактов

stopWatch.Start();

//Вызов функции последовательного поиска

nom = Function.Posl(textBox1.Text, str);

//Остановка счетчика тактов

stopWatch.Stop();

TimeSpan ts = stopWatch.Elapsed;

string elapsedTime = Convert.ToString(ts.Ticks);

//Вывод сообщения с количеством тактов процессора

MessageBox.Show(elapsedTime, "Количество тактов процессора");

//Если строка номеров не пустая

if (nom != "")

{

//Вывод результата поиска

MessageBox.Show("Данный фрагмент встречается с " + nom + "-го номера", "Результат поиска");

//Открываем файл, в котором выполнялся поиск System.Diagnostics.Process.Start(openFileDialog1.FileName);

}

//Вывод сообщения о неудачном поиске

else MessageBox.Show("Данный фрагмент не встречается в тексте", "Результат поиска");

}

//Если выбран алгоритм Рабина-Карпа

if (radioButton2.Checked == true)

{

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

//Вызов функции поиска алгоритмом Рабина

nom = Function.Rabina(textBox1.Text, str);

stopWatch.Stop();

TimeSpan ts = stopWatch.Elapsed;

string elapsedTime = Convert.ToString(ts.Ticks);

MessageBox.Show(elapsedTime, "Количество тактов процессора");

if (nom != "")

{

MessageBox.Show("Данный фрагмент встречается с " + nom + "-го номера", "Результат поиска"); //Открываем файл, в котором выполнялся поиск System.Diagnostics.Process.Start(openFileDialog1.FileName);

}

else MessageBox.Show("Данный фрагмент не встречается в тексте", "Результат поиска");

}

//Если выбран алгоритм КМП

if (radioButton3.Checked == true)

{

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

//Вызов функции поиска алгоритмом КМП

nom = Function.KMP(textBox1.Text, str);

stopWatch.Stop();

TimeSpan ts = stopWatch.Elapsed;

string elapsedTime = Convert.ToString(ts.Ticks);

MessageBox.Show(elapsedTime, "Количество тактов процессора");

if (nom != "")

{

MessageBox.Show("Данный фрагмент встречается с " + nom + "-го номера", "Результат поиска"); //Открываем файл, в котором выполнялся поиск System.Diagnostics.Process.Start(openFileDialog1.FileName);

}

else MessageBox.Show("Данный фрагмент не встречается в тексте", "Результат поиска");

}

//Если выбран алгоритм БМ

if (radioButton4.Checked == true)

{

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

//Вызов функции алгоритмом БМ

nom = Convert.ToString(Function.BM(textBox1.Text,str));

stopWatch.Stop();

TimeSpan ts = stopWatch.Elapsed;

string elapsedTime = Convert.ToString(ts.Ticks);

MessageBox.Show(elapsedTime,"Количество тактов процессора");

if (nom != "")

{

MessageBox.Show("Данный фрагмент встречается с " + nom + "-го номера", "Результат поиска"); System.Diagnostics.Process.Start(openFileDialog1.FileName);

}

else MessageBox.Show("Данный фрагмент не встречается в тексте", "Результат поиска");

}

}

}

//Включение кнопки "Выполнить поиск", после выбора алгоритма

private void radioButton1_CheckedChanged(object sender, EventArgs e)

{

button3.Enabled = true;

}

//Включение кнопки "Выполнить поиск", после выбора алгоритма

private void radioButton3_CheckedChanged(object sender, EventArgs e)

{

button3.Enabled = true;

}

//Включение кнопки "Выполнить поиск", после выбора алгоритма

private void radioButton2_CheckedChanged(object sender, EventArgs e)

{

button3.Enabled = true;

}

//Включение кнопки "Выполнить поиск", после выбора алгоритма

private void radioButton4_CheckedChanged(object sender, EventArgs e)

{

button3.Enabled = true;

}

}

}

Код библиотеки классов:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

namespace Fuction

{

public static class Function

{

//Функция последовательного поиска

public static string Posl(string x, string s)

{

представлена в Приложении А

}

//Вычисление хеш-функции для алгоритма Рабина

public static int Hash(string s)

{

представлена в Приложении Б

}

//Функция поиска алгоритмом Рабина

public static string Rabina(string x, string s)

{

представлена в Приложении Б

}

//Составление префикс-функции для КМП

public static int[] PrefFunc(string x)

{

представлена в Приложении В

}

//Функция поиска алгоритмом КМП

public static string KMP(string x, string s)

{

представлена в Приложении В

}

//Таблица смещений для БМ

public static void ShiftBM(string X)

{

представлена в Приложении Г

}

//Функция поиска алгоритмом БМ

public static string BM(string X, string S)

{

представлена в Приложении Г

}

}

}

Приложение Е

Результаты экспериментов

Таблица 2. Результаты экспериментов.

Символы	№ опыта	Алгоритмы поиска
		Простой	Рабина-Карпа	КМП	БМ
1000	1	1681	1391	1650	1404
	2	1687	1798	1632	1410
	3	1675	1693	1651	1385
	4	1699	1706	1638	1391
	5	1687	1749	1644	1373
	6	1681	1810	1656	1428
	7	1687	1699	1650	1502
	8	1693	1736	1638	1416
	9	1706	1816	1657	1379
	10	1675	1780	1656	1453
10000	1	10359	11320	9583	4890
	2	10236	11135	9805	7415
	3	10372	11333	9497	4551
	4	10347	10852	9596	4816
	5	10273	10994	9676	6535
	6	6319	6892	9626	4871
	7	10436	11012	9805	5919
	8	10335	9981	9959	7231
	9	10483	10403	9639	4921
	10	10372	11326	9922	7181
100000	1	100353	98760	91520	36893
	2	99587	99606	92212	54706
	3	100408	98548	94902	63040
	4	99965	108937	91890	39715
	5	101217	102341	91410	46206
	6	100846	99763	91871	44828
	7	100932	101016	92450	37078
	8	99989	100542	93639	53210
	9	101006	104232	92370	52822
	10	98727	99262	92267	54131

В Таблице 2 алгоритм Кнута-Морриса-Пратта обозначен как КМП, и алгоритм Бойера-Мура как БМ.

Курсовая работа «Поиск подстроки в строке» выполнена мною самостоятельно, и на все источники, имеющиеся в работе, даны соответствующие ссылки.

Размещено на Allbest.ru