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

Алгоритмы и структуры данных

на тему: "Сравнение строк"

Оглавление

• Введение
• 1. Детальная постановка задачи
• 2. Теоретическое введение
• 2.1 Функции сравнения строк
• 2.2 Алгоритм Кнута-Морриса-Пратта (КМР)
• 2.3 Алгоритм Бойера-Мура (БМ)
• 3. Модель по "Сравнение строк"
• 4. Входные и выходные данные по "сравнение строк"
• 4.1Входные данные ПО "сравнение строк"
• 4.2Выходные данные для ПО "сравнение строк"
• 5. Архитектурное проектирование
• 6. Проектирование по "сравнение строк"
• 7. Описание классов проекта "сравнение строк"
• 7.1Общая структура классов проекта ПО "Сравнение строк"
• 7.2Подробное описание классов проекта ПО "Сравнение строк"
• Выводы
• Список используемой литературы
• Приложение
• Введение
• Цель работы
• Изучить и реализовать основные принципы алгоритмов и структур данных проекта "Сравнение строк".
• Написать демонстрационную программу, в которой будут использоваться реализованная структура данных и показать работоспособность созданной структуры данных проекта " Сравнение строк".
• Изучить методы Кнута - Морриса - Пратта и Бойера - Мура, которые предназначены для сравнения строк и использовать их в разработки проекта.
• Спроектировать методы проекта " Сравнение строк".
• По заданию курсового проекта необходимо создать класс который реализует методы сравнения строк методом Кнута - Морриса - Пратта.
• Создать класс который реализует сравнение строк методом Бойера - Мура.
• Входные данные в программу вводятся в ячейки, предназначенные для ввода данных. При нажатии на кнопки с соответствующими названиями алгоритмов сравнения строк, выводится результат в поле с выходными данными. Так же отображается промежуточное значение сравнения строк.
• 1. Детальная постановка задачи

алгоритм программный строка класс

Разработать программу реализации сравнения строк по алгоритмам Кнута-Морриса-Пратта и Бойера-Мура с визуализацией основных этапов сравнения.

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

Для решения системы выбрать любой из существующих методов.

Особенности:

-Программа реализована на языке С++ с использованием интегрированной среды разработки Visual Studio 2012.

- При выводе на экран используются компоненты экранной формы

- В данной программе используется

Программа должна отвечать следующим требованиям

­ Обеспечивать вывод промежуточных значений на экран;

­ Обеспечивать правильный вывод данных на экран;

­ Выводить сообщения об ошибке при некорректности заполнения полей;

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

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

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

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

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

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

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

Рисунок 2.2.1 - Начало построения автомата для поиска подстроки hello

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



Рисунок 2.2.2 - Полный автомат Кнутта- Морриса - Пратта для подстроки ababcb

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

subLoc = 1// указатель текущего сравниваемого символа в подстроке

textLoc = 1// указатель текущего сравниваемого символа в тексте

while textLoc <= length(text) and subLoc <= length(substring) do

if subLoc = 0 or text[textLoc] = substring[subLoc] then

textLoc = textLoc + 1

subLoc = subLoc + 1

else// совпадения нет; переход по несовпадению

subLoc = fail[subLoc]

end if

end while

if (subLoc > length(substring)) then

return textLoc - length(substring) + 1//найденное совпадение

else

return 0// искомая подстрока не найдена

end if

Прежде, чем перейти к анализу этого процесса, можно рассмотреть как задаются переходы по несовпадению. Можно заметить, что при совпадении ничего особенного делать не надо: происходит переход к следующему узлу. Напротив, переходы по несовпадению определяются тем, как искомая подстрока соотносится сама с собой. Например, при поиске подстроки ababcb нет необходимости возвращаться назад на четыре позиции при необнаружении символа c. На пятом символе в образце можно понять, что первые четыре символа совпали, и поэтому символы ab в тексте, отвечающие третьему и четвертому символам образца, совпадают также с первым и вторым символами образца.

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

Алгоритм Бойера -- Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях -- часть проверок пропускаются как заведомо не дающие результата.

Общая оценка вычислительной сложности алгоритма -- O(|haystack|+|needle|+|У|) на непериодических шаблонах и O(|haystack|·|needle|+|У|) на периодических, где haystack -- строка, в которой выполняется поиск, needle -- шаблон поиска, У -- алфавит, на котором проводится сравнение. В 1991 году Коул показал, что на непериодических шаблонах за полный проход по строке алгоритм совершит не более 3·|haystack| сравнений.

Алгоритм

Алгоритм основан на трёх идеях.

Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

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

Эвристика стоп-символа. Предположим, что мы производим поиск слова "колокол". Первая же буква не совпала -- "к" (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней буквы "к".

Строка: * * * * * * к * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.

Строка: * * * * * а л * * * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Если стоп-символ "к" оказался за другой буквой "к", эвристика стоп-символа не работает.

Строка: * * * * к к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л ?????

В таких ситуациях выручает третья идея АБМ -- эвристика совпавшего суффикса.

Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Строка: * * т о к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае совпал суффикс "окол", и шаблон сдвигается вправо до ближайшего "окол". Если подстроки "окол" в шаблоне больше нет, но он начинается на "кол", сдвигается до "кол", и т. д.

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

Достоинства

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

Недостатки

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

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

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

На искусственно подобранных "неудачных" текстах (например, needle = "колоколоколоколоколокол") скорость алгоритма Бойера-Мура серьёзно снижается. Существуют попытки совместить присущую алгоритму Кнута-Морриса-Пратта эффективность в "плохих" случаях и скорость Бойера-Мура в "хороших" -- например, турбо-алгоритм, обратный алгоритм Колусси и другие.

Просмотрев оба метода сравнения строк можно вывести таблицу сравнений скорости сравнения (см. табл. 2.4)

Таблица 2.4- Сравнительная таблица методов решения уравнений

Алгоритм	Время выполнения
	Длина ?10	Длина ?100	Длина ?250
КМП	5	30	50
БМ	31	31	32

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

Для реализации поставленной задачи необходимо создать минимум три класса (см.рис. 3.1):

1. BM -- класс, который реализует алгоритм Бойера - Мурра.

2. KMP -- класс, который реализует алгорит Кнута - Морриса - Пррата.

3. Convert -- класс, который будет совершать преобразование типов.

Рисунок 3.1- Предложенные классы реализации

Класс KMP должен представлять собой алгоритм поиска строки методом Кнута - Мойера - Пратта. Он должен содержать следующие поля:

1. int i - позиции, на которой идет сравнение;

2. int j - индекс префикс - функции;

3. int strLength - вводимая строка;

4. int strToSearchLength - строка, которую ищем;

Кроме полей, данный класс должен содержать так же следующие методы.

1. Поиск префикс - функции;

2. Поиск подстроки.

Класс BM должен представлять собой структуру двумерного массива. Од должен содержать следующие поля:

1. int k - значение префикс функции;

Кроме полей, данный класс должен содержать так же следующие методы.

1. Вычисление префикс - функции;

2. Поиск подстроки.

Класс Convert конвертирует типы. Данный класс, содержит, так же следующие методы:

ѕ public члены:

1. template<class T> class TryToResult - результат выполнения Try-функций, содержит bool success - успешна ли операция, T value - результат);

2. static TryToResult<double> tryToDouble(Platform::String^ value) - перевод Platform::String^ value в double, входные параметры: Platform::String^ строка, выходные параметры: результат Try-функций;

3. static TryToResult<double> tryToDouble(std::string value) - перевод Platform::String^ value в double, входные параметры: std::string строка, параметры: результат Try-функций;

4. static TryToResult<int> tryToInt(Platform::String^ value) - перевод Platform::String^ value в int, входные параметры: std::string строка, выходные параметры: результат Try-функций;

5. static std::string toStdString(double value) - перевод double в std::string, входные параметры: число, выходные параметры: std::string строка;

6. static std::string toStdString(const wchar_t* value) - перевод const wchar_t* в std::string, входные параметры: const wchar_t* строка, выходные параметры: std::string строка;

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

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

Входными данными в программе являются следующие данные, которые вводят в поля:

str -- строка, которую вводит пользователь;

strToSearch -- искомая подстрока;

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

I - индекс первой найденной подстроки в строке;

Если введена пустая строка для сравнения, то система выводит сообщение об ошибке. В случае, если подстрока не найдена, ПО выводит информацию в поле со значением равным -1.

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

Структура проекта может быть представлена моделями двух типов: логической и физической. Логическая модель отражает классы, связь между ними, а область рассмотрения обычно ограничена теми классами, которые отражают предметную область. В качестве средства отображения используют UML-диаграммы, (см. рис. 5.1).

Рисунок 5.1 - Диаграмма классов для представления ПО "Сравнение строк"

Физическая модель проекта ПО "Сравнение строк "представлена на рисунку 5.2



Рисунок 5.2 - Физическая модель проекта ПО "Сравнение строк"

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

Исходя из поставленной задачи выполняем проектирование методов программы "сравнение строк".

Метод KMP::find-- метод сравнения строк по алгоритму Кнута - Мойера - Пратта:

int KMP::find (const char str[], const char strToSearch[])

{

целое i = 0;

целое j = 0;

целое strLength = strlen(str);

целое strToSearchLength = strlen(strToSearch);

out = "prefixFunction(strToSearch)" + "\n";

целое *prefixFunc = prefixFunction(strToSearch);

out += "Search \n";

/* поиск */

find(prefixFunc, str, strToSearch, i, j);

free (prefixFunc); /* освобождение памяти массива d */

если (j == strToSearchLength){

out += "result " + i + "-" + j + "=" + (i - j) + "\n";

возврат i-j;

конец если

иначе /* i==N */

конец цикла

out += "result = -1\n";

возврат -1;

конец цикла

конец метода

Метод KMP::prefixFunction выполняет поиск префикс - функции в алгоритме Кнута - Мойера - Пратта;

целое* KMP::prefixFunction(const char strToSearch[])

{

целое strToSearchLength = strlen(strToSearch);

целое *prefixFunc = (int*)malloc(strToSearchLength*sizeof(int));

prefixFunc[0]=-1;

out += prefixFunc[0] + "\n";

для i = 0, j = -1 пока i < strToSearchLength -1 шаг 1;

{

Пока (j >= 0) и (strToSearch[j] != strToSearch[i]))

j = prefixFunc[j];

i++;

j++;

если (strToSearch[i] == strToSearch[j])

prefixFunc[i] = prefixFunc[j];

иначе

prefixFunc[i]= j;

out += prefixFunc[i] + "\n";

конец цикла

возврат prefixFunc;

конец метода

Метод BM::prefix_func-- метод поиска префикс - функции по алгоритму Бойера - Мурра.

vector<int> BM::prefix_func(const string &str) {

vector<int> p(str.length());

целок k = 0;

p[0] = 0;

out += p[0] + "\n";

для (int i = 1; i < str.length(); пока ++i) {

пока (k > 0 && str[k] != str[i]) {

k = p[k - 1];

}

если (str[k] == str[i]) {

++k;

}

p[i] = k;

out += p[i] + "\n";

конец цикла

возврат p;

конец метода

Метод BM::find-- метод поиска подстроки в строке алгоритмом Бойера - Мурра.

целое BM::find(string &str, string &strToSearch) {

если (str.length() < strToSearch.length()) {

возврат -1;

конец цикла

если (!strToSearch.length()) {

возврат str.length();

конец цикла

//состовление страницы

typedef hash_map<char, int> TStopTable;

typedef hash_map<int, int> TSufficsTable;

TStopTable stop_table;

TSufficsTable suffics_table;

out = "stop_table \n";

для i = 0; i < strToSearch.length() до ++i шаг 1{

stop_table[strToSearch[i]] = i;

out += ((char)strToSearch[i]).ToString() + " " + i + "\n";

конец цикла

string rt(strToSearch.rbegin(), strToSearch.rend());

vector<int> p = prefix_func(strToSearch);

out += "prefix_func(strToSearch) \n";

vector<int> pr = prefix_func(rt);

out += "prefix_func(\"" + Convert::toPlatformString(rt.c_str()) +"\") \n";

out += "suffics_table \n";

для (int i = 0; i < strToSearch.length() + 1; ++i) {

suffics_table[i] = strToSearch.length() - p.back();

out += suffics_table[i] + "\n";

конец цикла

out += "suffics_table (step2)\n";

для ( i = 1; i < strToSearch.length(); ++i) {

целое j = pr[i];

suffics_table[j] = min(suffics_table[j], i - pr[i] + 1);

out += suffics_table[i] + "\n";

конец цикла

out += "shift\n";

для (shift = 0; shift <= str.length() - strToSearch.length();) {

int pos = strToSearch.length() - 1;

пока (strToSearch[pos] == str[pos + shift]) {

если (pos == 0) return shift;

--pos;

Конец цикла

если (pos == strToSearch.length() - 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);

shift += stop_symbol_additional;

конец цикла

если

{

shift += suffics_table[strToSearch.length() - pos - 1];

конец цикла

out += shift + "\n";

конец цикла

возврат -1;

конец метода

Метод TryToResult - результат выполнения Try-функций, содержит bool success - успешна ли операция, T value - результат);

template<class T>

Convert::TryToResult<T> Convert::tryTo(std::string value)

{

TryToResult<double> result;

int index = 0;

if(value[index] == '-')

index++;

if(!isDigit(value[index]))

{

result.succeess = false;

result.value = 0;

}

else

{

result.succeess = true;

result.value = ::atof(value.c_str());

}

return result;

}

Метод static TryToResult - перевод Platform::String^ value в double, входные параметры: Platform::String^ строка, выходные параметры: результат Try-функций;

template<class T>

Convert::TryToResult<T> Convert::tryTo(Platform::String^ value)

{

std::wstringstream convertor;

Convert::TryToResult<T> result;

convertor << value->Data();

convertor >> result.value;

если (convertor.bad() или convertor.fail())

начало цикла

result.value = 0;

result.succeess = false;

конец цикла

иначе

начало цикла

result.succeess = true;

конец цикла

возврат result;

конец метода

Метод static TryToResult<double> tryToDouble(std::string value) - перевод Platform::String^ value в double, входные параметры: std::string строка, параметры: результат Try-функций;

Convert::TryToResult<double> Convert::tryToDouble(std::string value)

{

TryToResult<double> result;

int index = 0;

если (value[index] == '-')

index++;

если (!isDigit(value[index]))

конец цикла

result.succeess = false;

result.value = 0;

конец цикла

иначе

начало цикла

result.succeess = true;

result.value = ::atof(value.c_str());

конец цикла

возврат result;

конец метода

После алгоритмов, которые были спроектированы, можно приступить к кодированию.

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

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

После проектирование классов, произведем описание классов и их методов.

КМР

Является классом для поиска префикс функции и поиска сравнения подстроки в строке. Он содержит следующие поля:

- int i - позиции, на которой идет сравнение;

- int j - индекс префикс - функции;

- int strLength - вводимая строка;

- int strToSearchLength - строка, которую ищем;

Методы:

- KMP::find - реализует алгоритм поиска подстроки в строке;

- KMP::prefixFunction - реализует поиск префикс - функции;

Класс BMP

Реализовывает поиск подстроки в строке методам Бойера - Мурра. Содержит следующую информацию. Поля класса:

1. I - индекс первой найденной подстроки в строке;

Методы класса:

- BM::prefix_func--метод для поиск префикс - функции;

- BM::find- метод для поиска подстроки в строке;

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

Класс КМР

Класс, который реализует поиск подстроки в строке по алгоритму Кнута - Мойера - Пратта.

#pragma once

class KMP

{

private:

Platform::String^ out;

public:

KMP(void);

~KMP(void);

int find (const char str[], const char strToSearch[]);

void KMP::find(int* prefixFunc, const char str[], const char strToSearch[], int &i, int &j);

int* KMP::prefixFunction(const char strToSearch[]);

Platform::String^ output();

};

Содержит следующие поля:

- int i - позици, на которой идет сравнение;

- int j - идекс префикс - функции;

- int strLength - вводимая строка;

- int strToSearchLength - строка, которую ищем;

Методы:

- KMP::find - реализует алгоритм поиска подстроки в строке;

- KMP::prefixFunction - реализует поиск префикс - функции;

- Platform::String^ output(); - вывод промежуточных значений.

Класс ВМ

Класс, реализующий поиск подстроки в строке по алгоритму Бойера - Мурра.

Структура класса приведена ниже:

#pragma once

using namespace std;

class BM

{

private:

Platform::String^ out;

public:

BM(void);

~BM(void);

vector<int> BM::prefix_func(const string &s);

int BM::find(string &s, string &t);

Platform::String^ output();

};

Содержит следующие методы:

- BM::prefix_func--метод для поиск префикс - функции;

- BM::find- метод для поиска подстроки в строке;

- Platform::String^ output(); - вывод промежуточных значений.

Конструктор класса КМР

KMP(void);

Предназначен для поиска подстроки методом Кнута- Мойера - Пратта.

Уровень доступа:

Public

Параметры:

int str -- строка, которую вводит пользователь;

int strToSearch-- искомая подстрока.

Возвращаемое значение:

Нет

Исключения:

Нет

Конструктор класса ВМ

Предназначен для поиска подстроки методом Бойера - Мурра.

Уровень доступа:

Public

Параметры:

int I - индекс первой найденной подстроки в строке;

Возвращаемое значение:

Нет

Исключения:

Нет

Листинг кода программы и результаты ее работы приведены в приложении А и Б.

Выводы

Детально изучена тема курсового проекта. Описаны алгоритмы поиска подстроки методами Кнута - Мойера - Пратта. Приведены примеры поиска подстроки методами Кнута - Мойера - Пратта и Бойера - Мурра.

Описаны входные и выходные данные и формы ПО сравнения строк.

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

Согласно своему варианту создано три класса с полями и методами:

- KMP -- класс, который реализует поиск подстроки в строке по методу Кнута - Мойера -Пратта.

- BM -- класс, который реализует поиск подстроки в строке по методу Бойера - Мурра.

- Convert-- класс, который конвертирует типы для вывода на рабочую форму.

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

Написана демонстрационная программа, в которой используется реализованная структура данных

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

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

1. Дональд Кнут. Том 1 " Искусство программирования Основные алгоритмы. " 2010г.

2. http://chasolimp.ucoz.com/publ/5-1-0-8 - метод Кнута - Мойера - Пратта

3. http://algolib.narod.ru/Search/BoyerMur.html - метод Бойера - Мурра.

4. Методичка кафедры( стр.31 М.В.Кузнецова, Н.Г.Мокляк, Л.И.Черноштан "Руководство для самостоятельной работы при изучении программирования")

5. Кормен и Ко. Алгоритмы: построение и анализ. 2-е издание. 1296с.

6. Левитин. Алгоритмы: введение в разработку и анализ. 2006. ?576с.

7. Никлаус Вирт Алгоритмы и структуры данных. -- М.: Невский Диалект, 2006. С. 352

Приложение А

Листинг исходного кода

Листинг файла КМР.cpp

#include "pch.h"

#include "KMP.h"

#include <iostream>

#include <string.h>

#include <time.h>

#include <stdlib.h>

using namespace std;

KMP::KMP(void)

{

}

KMP::~KMP(void)

{

}

int KMP::find (const char str[], const char strToSearch[])

{

int i = 0;

int j = 0;

int strLength = strlen(str);

int strToSearchLength = strlen(strToSearch);

out = "prefixFunction(strToSearch)" + "\n";

int *prefixFunc = prefixFunction(strToSearch);

out += "Search \n";

/* поиск */

find(prefixFunc, str, strToSearch, i, j);

free (prefixFunc); /* освобождение памяти массива d */

if (j == strToSearchLength){

out += "result " + i + "-" + j + "=" + (i - j) + "\n";

return i-j;

}

else /* i==N */ {

out += "result = -1\n";

return -1;

}

}

void KMP::find(int* prefixFunc, const char str[], const char strToSearch[], int &i, int &j)

{

int strLength = strlen(str);

int strToSearchLength = strlen(strToSearch);

for( i = 0, j = 0; (i < strLength) && (j < strToSearchLength); i++, j++) {

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

j = prefixFunc[j];

out += "i = " + i + "j = " + j + "\n";

}

}

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

int* KMP::prefixFunction(const char strToSearch[])

{

int strToSearchLength = strlen(strToSearch);

int *prefixFunc = (int*)malloc(strToSearchLength*sizeof(int));

prefixFunc[0]=-1;

out += prefixFunc[0] + "\n";

for(int i = 0, j = -1; i < strToSearchLength -1;)

{

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

j = prefixFunc[j];

i++;

j++;

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

prefixFunc[i] = prefixFunc[j];

else

prefixFunc[i]= j;

out += prefixFunc[i] + "\n";

}

return prefixFunc;

}

Platform::String^ KMP::output()

{

return out;

}

Листинг BM.cpp

#include "pch.h"

#include "BM.h"

#include <cstdlib>

#include <iostream>

#include <string>

#include <hash_map>

#include <Convert.h>

#define ALPHABET_LEN 255

#define NOT_FOUND patlen

#define max(a, b) ((a < b) ? b : a)

using namespace std;

BM::BM(void)

{

}

BM::~BM(void)

{

}

vector<int> BM::prefix_func(const string &str) {

vector<int> p(str.length());

int k = 0;

p[0] = 0;

out += p[0] + "\n";

for (int i = 1; i < str.length(); ++i) {

while (k > 0 && str[k] != str[i]) {

k = p[k - 1];

}

if (str[k] == str[i]) {

++k;

}

p[i] = k;

out += p[i] + "\n";

}

return p;

}

int BM::find(string &str, string &strToSearch) {

if (str.length() < strToSearch.length()) {

return -1;

}

if (!strToSearch.length()) {

return str.length();

}

typedef hash_map<char, int> TStopTable;

typedef hash_map<int, int> TSufficsTable;

TStopTable stop_table;

TSufficsTable suffics_table;

out = "stop_table \n";

for (int i = 0; i < strToSearch.length(); ++i) {

stop_table[strToSearch[i]] = i;

out += ((char)strToSearch[i]).ToString() + " " + i + "\n";

}

string rt(strToSearch.rbegin(), strToSearch.rend());

vector<int> p = prefix_func(strToSearch);

out += "prefix_func(strToSearch) \n";

vector<int> pr = prefix_func(rt);

out += "prefix_func(\"" + Convert::toPlatformString(rt.c_str()) +"\") \n";

out += "suffics_table \n";

for (int i = 0; i < strToSearch.length() + 1; ++i) {

suffics_table[i] = strToSearch.length() - p.back();

out += suffics_table[i] + "\n";

}

out += "suffics_table (step2)\n";

for (int i = 1; i < strToSearch.length(); ++i) {

int j = pr[i];

suffics_table[j] = min(suffics_table[j], i - pr[i] + 1);

out += suffics_table[i] + "\n";

}

out += "shift\n";

for (int shift = 0; shift <= str.length() - strToSearch.length();) {

int pos = strToSearch.length() - 1;

while (strToSearch[pos] == str[pos + shift]) {

if (pos == 0) return shift;

--pos;

}

if (pos == strToSearch.length() - 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);

shift += stop_symbol_additional;

} else {

shift += suffics_table[strToSearch.length() - pos - 1];

}

out += shift + "\n";

}

return -1;

}

Platform::String^ BM::output()

{

return out;

}

Листинг файла Convert.cpp

#include "pch.h"

#include "Convert.h"

Platform::String^ Convert::toPlatformString(const char* value)

{

std::string s_str(value);

std::wstring w_str(s_str.begin(), s_str.end());

return ref new Platform::String(w_str.c_str());

}

std::string Convert::toStdString(const wchar_t* value)

{

std::wstring w_str(value);

return std::string(w_str.begin(), w_str.end());

}

template<class T>

Convert::TryToResult<T> Convert::tryTo(std::string value)

{

TryToResult<double> result;

int index = 0;

if(value[index] == '-')

index++;

if(!isDigit(value[index]))

{

result.succeess = false;

result.value = 0;

}

else

{

result.succeess = true;

result.value = ::atof(value.c_str());

}

return result;

}

template<class T>

Convert::TryToResult<T> Convert::tryTo(Platform::String^ value)

{

std::wstringstream convertor;

Convert::TryToResult<T> result;

convertor << value->Data();

convertor >> result.value;

if(convertor.bad() || convertor.fail())

{

result.value = 0;

result.succeess = false;

}

else

{

result.succeess = true;

}

return result;

}

Convert::TryToResult<double> Convert::tryToDouble(Platform::String^ value)

{

return tryTo<double>(value);

}

Convert::TryToResult<double> Convert::tryToDouble(std::string value)

{

TryToResult<double> result;

int index = 0;

if(value[index] == '-')

index++;

if(!isDigit(value[index]))

{

result.succeess = false;

result.value = 0;

}

else

{

result.succeess = true;

result.value = ::atof(value.c_str());

}

return result;

}

Convert::TryToResult<int> Convert::tryToInt(Platform::String^ value)

{

return tryTo<int>(value);

}

std::string Convert::toStdString(double value)

{

std::ostringstream convertor;

convertor << value;

return convertor.str();

}

std::vector<std::string> Convert::splitByGraps(std::string text)

{

std::vector<std::string> tokens;

std::istringstream iss(text);

std::copy(std::istream_iterator<std::string>(iss),

std::istream_iterator<std::string>(),

std::back_inserter<std::vector<std::string> >(tokens));

return tokens;

}

bool Convert::isDigit(char value)

{

if(value > '9' || value < '0')

return false;

return true;

}

Приложение Б

Результаты работы программы

Рисунок Б.1 - Результат работы программы сравнения строк алгоритмом Кнута - Моейра - Пратта.

Рисунок Б.2 - Результат работы программы сравнения строк алгоритмом Бойера - Мурра.

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

...