Лабораторная работа 5. Алгоритмы поиска в тексте. Цель работы: изучить основные алгоритмы поиска в тексте и научиться решать задачи поиска в тексте на основе алгоритмов прямого поиска; Кнута

Цель работы: изучить основные алгоритмы поиска в тексте и научиться решать задачи поиска в тексте на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура.

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

Задания к лабораторной работе.

Выполните приведенные ниже задания.

1. На основании приведенных функций реализуйте алгоритмы поиска подстроки в строке.

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

Формат входных данных

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

Формат выходных данных

В выходной файл нужно вывести одно число – ответ на задачу.

Пример входного файла input.txt

abababa

Пример выходного файла output.txt

3. Даны две строки a и b. Требуется найти максимальную длину префикса строки a, который входит как подстрока в строку b. При этом считать, что пустая строка является подстрокой любой строки.

Формат входных данных

В первой строке входного файла содержится строка a, во второй – строка b. Элементами строк a и b являются произвольные символы с кодами ASCII больше 32. Длина каждой строки от 1 до 30000.

Формат выходных данных

В выходной файл вывести искомую длину префикса строки a, т.е. целое число от 0 до длины строки a.

Пример входного файла input.txt

abcdefghijklmnopqrstuvwxyz

Abcd?aBcd!abCd.abcD!?

Пример выходного файла output.txt

4. Назовем строку палиндромом, если она одинаково читается слева направо и справа налево. Примеры палиндромов: "abcba", "55", "q", "xyzzyx". Требуется для заданной строки найти максимальную по длине ее подстроку, являющуюся палиндромом.

Формат входных данных

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

Формат выходных данных

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

Пример входного файла input.txt

a123bc9e9c321

Пример выходного файла output.txt

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

· изучить словесную постановку задачи, выделив при этом все виды данных;

· сформулировать математическую постановку задачи;

· выбрать метод решения задачи, если это необходимо;

· разработать графическую схему алгоритма;

· записать разработанный алгоритм на языке С++;

· разработать контрольный тест к программе;

· отладить программу;

· представить отчет по работе.

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

· Титульный лист.

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

· Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке.

· Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Блок-Схема алгоритма.

· Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010.

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

· Выводы по лабораторной работе.

· Ответы на контрольные вопросы.

//описание функции алгоритма Бойера и Мура

int BMSearch(char *string, char *substring){

int sl, ssl;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

if (sl == 0)

cout << "Неверно задана строка\n";

else if (ssl == 0)

cout << "Неверно задана подстрока\n";

else {

int i, Pos;

int BMT[256];

for (i = 0; i < 256; i ++)

BMT[i] = ssl;

for (i = ssl-1; i >= 0; i--)

if (BMT[(short)(substring[i])] == ssl)

BMT[(short)(substring[i])] = ssl - i - 1;

Pos = ssl - 1;

while (Pos < sl)

if (substring[ssl - 1]!= string[Pos])

Pos = Pos + BMT[(short)(string[Pos])];

else

for (i = ssl - 2; i >= 0; i--){

if (substring[i]!= string[Pos - ssl + i + 1]) {

Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;

break;

}

else

if (i == 0)

return Pos - ssl + 1;

cout << "\t" << i << endl;

}

}

return res;

}

//описание функции алгоритма Кнута, Морриса и Пратта

int KMPSearch(char *string, char *substring){

int sl, ssl;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

if (sl == 0)

cout << "Неверно задана строка\n";

else if (ssl == 0)

cout << "Неверно задана подстрока\n";

else {

int i, j = 0, k = -1;

int *d;

d = new int[1000];

d[0] = -1;

while (j < ssl - 1) {

while (k >= 0 && substring[j]!= substring[k])

k = d[k];

j++;

k++;

if (substring[j] == substring[k])

d[j] = d[k];

else

d[j] = k;

}

i = 0;

j = 0;

while (j < ssl && i < sl){

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

j = d[j];

i++;

j++;

}

delete [] d;

res = j == ssl? i - ssl: -1;

}

return res;

}