Изучение эффективных алгоритмов обработки строк, построение боров, Z-функций, алгоритм Кнута-Морриса-Пратта

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ П. О. СУХОГО

Факультет автоматизированных и информационных систем

Кафедра «Информационные технологии»

ОТЧЕТ   ПО   ЛАБОРАТОРНОЙ   РАБОТЕ   № 8

по дисциплине «Конструирование программ и языки программирования»

Выполнила:     студентка гр. ИТ-32

Принял:          преподаватель

Гомель 2013

ЛАБОРАТОРНАЯ РАБОТА №8

Цель: изучение эффективных алгоритмов обработки строк, построение боров, Z-функций, алгоритм Кнута-Морриса-Пратта.

Вариант 11

Задание:

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

Листингпрограммы:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

public static int FindSubstring(string input, string pattern)//поиск подстроки

{

int n = input.Length;//длина исходной строки

int m = pattern.Length;//длина искомой строки

if (0 == n) throw new ArgumentException("String mustn't be empty", "input");//прервать с ошибкой, если исходная строка пуста

if (0 == m) throw new ArgumentException("String mustn't be empty", "pattern");//прервать с ошибкой, если искомая строка пуста

string rez = string.Format(pattern + " # " + input);//соединить 2троки

int[] d = GetPrefixFunction(rez);//получить префиксфункцию

Console.WriteLine("Префикс функция");//

for (int k = 0; k < d.Length; k++) Console.Write(" " + d[k]);//вывод префиксфункции

Console.WriteLine();

Console.WriteLine(rez);//вывод объединенной строки

Console.WriteLine();

int kol = 0;

for (int i = m + 1; i < rez.Length; i++)

{

if (d[i] == m)

{

Console.WriteLine("Встречается в позиции: " + (i - 2 * m));//вывод посзиции в которой найдена строка

kol++;

}

}            Console.WriteLine("Количество подстрок в строке: " + kol);

return -1;

}

private static int[] GetPrefixFunction(string pattern)

{

int n = pattern.Length;//длина строки

int[] pi = new int[n];//префиксфункция

pi[0] = 0;//первый элемент всегда 0

for (int i = 1; i < n; i++) //идем по строке

{

int j = pi[i - 1];//записываем значение префиксфункции на предыдущей итерации

while (j > 0 && pattern[i] != pattern[j])//префикс>0 и последние символы не совпадают

j = pi[j - 1];//присвоить предыдущее значение префиксфункции

if (pattern[i] == pattern[j]) ++j;//если последние символы совпадают, то увеличить на 1 значение префикса

pi[i] = j;//присвоить значение префикса

}

return pi;//вернуть префиксфункцию

}

static void Main(string[] args)

{

Console.WriteLine("Введите строку:");

string str = Console.ReadLine();//ввод исходной строки

Console.WriteLine("Введите подстроку:");

string patt = Console.ReadLine();//ввод искомой строки

FindSubstring(str, patt);//найти patt в str

Console.ReadKey();

}

}

}

Вывод: изучили эффективные алгоритмы обработки строк, построение боров, Z-функций, алгоритм Кнута-Морриса-Пратта.