Сравнение строк - Курсовая работа

Алгоритмы и структуры данных на тему: "Сравнение строк"Изучить и реализовать основные принципы алгоритмов и структур данных проекта "Сравнение строк". Написать демонстрационную программу, в которой будут использоваться реализованная структура данных и показать работоспособность созданной структуры данных проекта "Сравнение строк". Изучить методы Кнута - Морриса - Пратта и Бойера - Мура, которые предназначены для сравнения строк и использовать их в разработки проекта.Разработать программу реализации сравнения строк по алгоритмам Кнута-Морриса-Пратта и Бойера-Мура с визуализацией основных этапов сравнения. Разработать класс, который обеспечивает работу разреженной циклической матрицы и используя экземпляры этого класса решить систему линейных алгебраических уравнений. Особенности:-Программа реализована на языке С с использованием интегрированной среды разработки Visual Studio 2012.Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html - страницы. На пятом символе в образце можно понять, что первые четыре символа совпали, и поэтому символы ab в тексте, отвечающие третьему и четвертому символам образца, совпадают также с первым и вторым символами образца. Алгоритм Бойера - Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведется поиск) шаблон сравнивается с исходным текстом не во всех позициях - часть проверок пропускаются как заведомо не дающие результата. Общая оценка вычислительной сложности алгоритма - O(|haystack| |needle| |?|) на непериодических шаблонах и O(|haystack|·|needle| |?|) на периодических, где haystack - строка, в которой выполняется поиск, needle - шаблон поиска, ? - алфавит, на котором проводится сравнение.Метод KMP::find-метод сравнения строк по алгоритму Кнута - Мойера - Пратта: int KMP::find (const char str[], const char STRTOSEARCH[]) Метод BM::prefix_func-метод поиска префикс - функции по алгоритму Бойера - Мурра. vector BM::prefix_func(const string &str) {vector p(str.length()); Метод BM::find-метод поиска подстроки в строке алгоритмом Бойера - Мурра. целое BM::find(string &str, string &STRTOSEARCH) {если (str.length() <STRTOSEARCH.length()) {возврат-1; Метод static TRYTORESULT - перевод Platform::String^ value в double, входные параметры: Platform::String^ строка, выходные параметры: результат Try-функций; Метод static TRYTORESULT TRYTODOUBLE(std::string value) - перевод Platform::String^ value в double, входные параметры: std::string строка, параметры: результат Try-функций;Приведены примеры поиска подстроки методами Кнута - Мойера - Пратта и Бойера - Мурра. Согласно своему варианту создано три класса с полями и методами: - KMP - класс, который реализует поиск подстроки в строке по методу Кнута - Мойера-Пратта. BM - класс, который реализует поиск подстроки в строке по методу Бойера - Мурра. В курсовом проекте реализованы два алгоритма поиска подстроки в строке.} vector BM::prefix_func(const string &str) {vector p(str.length()); } int BM::find(string &str, string &STRTOSEARCH) {if (str.length() <STRTOSEARCH.length()) {return-1; TSTOPTABLE::const_iterator stop_symbol = stop_table.find(str[pos shift]); int stop_symbol_additional = pos - (stop_symbol != stop_table.end() ? stop_symbol->second :-1); Platform::String^ Convert::TOPLATFORMSTRING(const char* value)Рисунок Б.1 - Результат работы программы сравнения строк алгоритмом Кнута - Моейра - Пратта.

Оглавление

Введение

1. Детальная постановка задачи

2. Теоретическое введение

2.1 Функции сравнения строк

2.2 Алгоритм Кнута-Морриса-Пратта (КМР)

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

3. Модель по "Сравнение строк"

4. Входные и выходные данные по "сравнение строк"

4.1Входные данные ПО "сравнение строк"

4.2Выходные данные для ПО "сравнение строк"

5. Архитектурное проектирование

6. Проектирование по "сравнение строк"

7. Описание классов проекта "сравнение строк"

7.1Общая структура классов проекта ПО "Сравнение строк"

7.2Подробное описание классов проекта ПО "Сравнение строк"

Выводы

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

Приложение