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

Предоплата всего

Подписываем
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
ГВУЗ “Донецкий национальный технический университет”
КП 6.050103-13-114140.001 ПЗ Кафедра программного обеспечения интеллектуальных систем
Курсовой проект
по дисциплине: «Алгоритмы и структуры данных»
Руководители:
__________ ст.пр. Ольшевский А.И.
(дата, подпись)
__________ ст.пр. Бычкова Е.В.
(дата, подпись)
Разработал:
______ ст.гр. ПОС-12а Ольмезов К.И.
(дата, подпись)
Донецк 2013
__________________________
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
(назва вищого навчального закладу)
Кафедра Программного обеспечения интеллектуальных систем _______________________
Дисциплина Алгоритмы и структуры данных__________________________
Специальность Программная инженерия___________________________________
Курс ________2_________ Группа _____ПОС-12а_______ семестр _________1__________
З А Д А Н И Е
на курсовой проект (роботу) студента
_______________ ___ _Ольмезова Константина Ивановича _________
1. Тема проекта (работы) Поиск подстроки с помощью конечных автоматов___________
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
2. Срок сдачи студентом законченного проекта (роботы) 12 декабря 2013 ода_______ ___
_______________________________________________________________________ _____
3. Выходные данные к проекту (роботы) Словарь предметной области., теория по_______
данному методу, программный код, реализующий метод поиска подстроки с помощью _ конечного автомата_______________________ _______________________________ ____ _____________________________________________________________________________
_____________________________________________________________________________
_____________________________________________________________________________
4. Содержание расчетно-пояснительной записки (перечень вопросов, которые подлежат разработки) Описание метода и алгоритма, выполняющего этот метод, листинг_________ программы _ _____ ________________ _____________ ____
______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
5. Перечень графического материала (с точным указанием обязательных чертежей) Экранные формы__ ___________________________________________________________
_____________________________________________________________________________
_____________________________________________________________________________
_____________________________________________________________________________
_____________________________________________________________________________
6. Дата выдачи задания _____________________09.09.13_____________________________
РЕФЕРАТ Пояснительная записка: 37 с., 7 рис., 2 источника, 4 прил. Объектом разработки является программа поиска подстроки в строке Целью курсового проекта является разработка программного продукта для поиска подстроки в строке и ознакомление с алгоритмом поиска подстроки с помощью конечного автомата ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ, ОО АНАЛИЗ, ОО ПРОЕКТИРОВАНИЕ, ОО ПРОГРАММИРОВАНИЕ, ДИАГРАММЫ, BOOCH, UML |
|||||||||
КП 6.050103-13-114140.001 ПЗ |
|||||||||
Фамилия |
Подпись |
Дата |
|||||||
Разработал |
Ольмезов К.И. |
Поиск подстроки с помощью конечного автомата |
Литера |
Лист |
Листов |
||||
Рук. проекта |
А.И. Ольшевский |
8 |
3 |
32 |
|||||
Е.В. Бычкова |
ДонНТУ, каф. ПОИС Группа ПОС-12а |
||||||||
Н. контроль |
А.И. Ольшевский |
||||||||
Е.В. Бычкова |
|||||||||
Зав. каф. |
А.И. Шевченко |
СОДЕРЖАНИЕ Введение ..............................................................................................................6 1. Постановка задачи ………….…………………………...…….…..................7 1.1. Описание предметной области …………………………….....…......…….7 1.2. Цели и задачи курсового проекта ...............................................................7 2. Выбор метода решения....................................................................................8 2.1. Теоретические данные..................................................................................8 2.2. Описание входных и выходных данных.....................................................8 2.3. Обоснование выбора структур данных.......................................................8 3. Метод решения…....………………………....……………………………….9 3.1. Описание метода поиска подстроки с помощью конечного автомата.....9 3.2. Алгоритм составления автомата по заданной подстроке..........................9 3.3. Нахождение z-функции строки..................................................................11 4. Исследование эффективности метода..........................................................13 4.1. Описание исследования..............................................................................13 4.2. Содержание тестов......................................................................................13 4.3. Таблица сравнения быстродействия..........................................................14 4.4. Анализ полученных результатов...............................................................14 ВЫВОДЫ ...........................................................................................................16 Приложение А Техническое задание…………………....…….……...…….18 Приложение В Руководство пользователя…………….....…………….......22 Приложение С Экранные формы……………………….…....…...….…......23 Приложение D Листинг программы……………….…………....….…..…..26 |
|||||
Разработал |
Фамилия |
Подпись |
Дата |
КП 6.050103-13-114140.001 ПЗ |
Лист |
Ст. гр. ПИ-12в |
Ольмезов К.И. |
4 |
|||
ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ, СОКРАЩЕНИЙ И ТЕРМИНОВ ПП Программный продукт ПО Программное обеспечение КА Конечный автомат |
|||||
Разработал |
Фамилия |
Подпись |
Дата |
КП 6.050103-13-114140.001 ПЗ |
Лист |
Ст. гр. ПОС-12а |
К.И. Ольмезов |
5 |
|||
ВВЕДЕНИЕ
Поиск информации одно из основных использований компьютера. Одна из простейших задач поиска информации поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна она применяется в текстовых редакторах, СУБД, поисковых машинах.
На сегодняшний день существует огромное разнообразие алгоритмов поиска подстроки. Программисту приходится выбирать подходящий в зависимости от различных факторов.
Объектом курсового проекта является поиск подстроки с помощью конечного автомата этот метод полезен если требуется находить вхождение одной заранее заданной подстроки в достаточно большое множество строк.
В процессе разработки предстоит решить следующие задачи:
1 ПОСТАНОВКА ЗАДАЧИ
1.1.Описание предметной области
Строка это массив символов, хранящийся в памяти компьютера. Алфавит строки множество используемых символов определяется произвольно в зависимости от задачи.
Пусть даны две строки и . Тогда строка является подстрокой в позиции если (нумерацию строк считаем с нуля, - длина строки S).
Задача поиска подстроки заключается в том, чтобы по заданным и определить, является ли подстрокой и если да, то определить позицию первого вхождения.
1.2. Цели и задачи курсового проекта
Задачи курсового проекта:
1. Составить алгоритм на основе метода поиска подстроки с помощью конечного автомата
2. Составить программу, реализующую алгоритм
Цели курсового проекта:
1. Реализовать программный продукт для поиска подстроки с помощью конечного автомата
1.3. Выбор средств
В качестве языка программирования будет использоваться C++, а в качестве среды разработки C++ Builder 6. Этот выбор обусловлен тем, что C++ Builder 6 интегрированная визуальная среда разработки и позволяет удобно разрабатывать оконные приложения.
2 ВЫБОР МЕТОДА РЕШЕНИЯ
2.1. Теоретические данные
Работа системы происходит в два этапа. На первом этапа вводится искомая подстрока, для которой сразу же после ввода программа составляет автомат. На втором этапе работа проходит в бесконечном цикле (выход по команде пользователя), на каждой итерации которого пользователь вводит строку, для которой будет осуществлён поиск подстроки по составленному автомату. При этом на каждой итерации бесконечного цикла пользователь может поменять искомую подстроку.
Ввод строки и подстроки может производится из клавиатуры и из файла. Поиск подстроки отображается в режиме реального времени с обозначением текущего состояния автомата в данный момент.
2.2. Описание входных и выходных данных
Входные данные:
подстрока, строка
Выходные данные:
позиция вхождение подстроки в строку (нумерация символов с единицы, если подстрока не входит в строку возвращается 0)
2.3. Обоснование структур данных
Будем представлять автомат в памяти компьютера как массив состояний автомата, каждое из которых определяется множеством переходов из него. Для удобства программирования при создании массива будем использовать контейнер стандартной библиотеки шаблонов vector.
Так как в большинстве случаев количество переходов из каждого состояния автомата невелико (1-2), нет смысла использовать для хранения переходов массив из 256 (по количеству символов) элементов в каждом состоянии.
Для хранении переходов будем использовать контейнер map<char,int>, ключами которого будут входные символы, а значение каждого элемента номер состояния, в которое будет осуществлён переход по этому символу. Если при поступлении очередного символа значение для него в текущем состоянии не определено, то происходит переход в нулевое состояние.
3. МЕТОД РЕШЕНИЯ
3.1. Описание метод поиска подстроки с помощью конечного автомата
Конечным автоматом называется структура, определяемая упорядоченной пятёркой: , где
Cчитается, что конечный автомат распознаёт некоторый язык (в данном случае состоящий из одного слова) если при работе на словах этого языка переходит в конечное состояние, а при работе на других словах нет.
Для каждой строки можно построить КА, распознающий её. После этого при прогоне по этому автомату любой строки можно проверить, содержит ли она заданную подстроку (узнав, было ли достигнуто конечное состояние).
Достигнув конечного состояния автомата, можно с уверенностью сказать, что на текущем символе оканчивается первое вхождение искомой подстроки в строку.
3.2. Алгоритм создания автомата по заданной подстроке
Для создания автомата будем использовать z-функцию строки (её нахождение будет описано далее).
Z-функция строки S такой массив Z длины N, что Z(i) длина наибольшего префикса строки S, с которым совпадает её подстрока, начинающаяся с i-того символа. Формально:
Z(0) всегда неопределённо (мы пример Z(0)=0).
Найдя Z-функцию построим автомат в несколько шагов:
В результате получим автомат с состояниями, где - начальное состояние, - конечное состояние. При подаче на этот автомат входной строки можно точно сказать входит ли и начиная с какого символа в эту строку подстрока, на основе которой был построен автомат.
Как видно, такой КА, при известной Z-функции строится за линейное время.
Пример
Рассмотрим подстроку S=”ababceabaxd”. Построим для неё распознающий её автомат.
Составим автомат из переходов при прямом проходе по строке.
Рисунок 3.1.1 первый шаг постройки автомата
Добавим рёбра для учёта повторения префиксов.
Рисунок 3.1.2 добавление учёта префиксов в автомат
3.3. Алгоритм вычисления z-функции строки
Z-функцию строки можно вычислить за линейное время (пропорциональное длине строки).
Чтобы получить эффективный алгоритм, будем вычислять значения по очереди от до , и при этом постараемся при вычислении очередного значения максимально использовать уже вычисленные значения. Для корректной работы алгоритма назначим z[0]=0.
Назовём для краткости подстроку, совпадающую с префиксом строки , отрезком совпадения. Например, значение искомой Z-функции это длиннейший отрезок совпадения, начинающийся в позиции (и заканчиваться он будет в позиции ).
Для этого будем поддерживать координаты самого правого отрезка совпадения, т.е. из всех обнаруженных отрезков будем хранить тот, который оканчивается правее всего. В некотором смысле, индекс это такая граница, до которой наша строка уже была просканирована алгоритмом, а всё остальное пока ещё не известно.
Тогда если текущий индекс, для которого мы хотим посчитать очередное значение Z-функции, это , мы имеем один из двух вариантов:
Для этого заметим, что подстроки и совпадают. Это означает, что в качестве начального приближения для можно взять соответствующее ему значение из отрезка , а именно, значение .
Однако значение могло оказаться слишком большим: таким, что при применении его к позиции оно "вылезет" за пределы границы . Этого допустить нельзя, т.к. про символы правее мы ничего не знаем, и они могут отличаться от требуемых.
Приведём пример такой ситуации, на примере строки aaaabaa
Когда мы дойдём до последней позиции (), текущим самым правым отрезком будет . Позиции с учётом этого отрезка будет соответствовать позиция , ответ в которой равен . Очевидно, что таким значением инициализировать нельзя, оно совершенно некорректно. Максимум, каким значением мы могли проинициализировать это , поскольку это наибольшее значение, которое не выходит за пределы отрезка .
Таким образом, в качестве начального приближения для безопасно брать только выражение
Проинициализировав таким значением , мы снова дальше действуем тривиальным алгоритмом потому что после границы , вообще говоря, могло обнаружиться продолжение отрезка совпадение, предугадать которое одними лишь предыдущими значениями Z-функции мы не могли.
4 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДА
4.1. Описание исследования
Проведём сравнительный анализ быстродействия, сравнив скорость работы метода конечного автомата со скоростью работы стандартной функции языка C и линейного поиска.
Запустим реализацию каждого из трёх методов поиска в цикле 1000000 итераций (для того, чтобы повысить время работы и сделать возможным его измерение).
Замерять время будем с помощью специальной функции clock() из библиотеки time.h, которая возвращает текущее количество миллисекунд, прошедших с 1 января 1970 года. Для получения времени работы методов узнаем значение времени до и после цикла и вычтем первое из второго.
4.2. Содержание тестов
Будем проводить исследование на различных входных данных:
4.3. Таблица сравнения быстродействия
Таблица 4.3.1 сравнительные данные времени работы различных алгоритмов поиска
Данные |
Время (мс, 1000000 запусков) |
|||
Строка |
Подстрока |
Стандартный поиск |
Линейный поиск |
Поиск через автомат |
abcdef |
OPQRSTUVWXYZ |
46 |
79 |
1687 |
12345 |
000000000000000 |
62 |
109 |
2094 |
012345 |
78901987894932190123979879230138 |
219 |
312 |
5657 |
mystring |
abcmysmymymmaystrmystringmysssam |
94 |
266 |
3640 |
aabab |
aeracbwqabaabaabadabaabaababaabq |
328 |
391 |
7359 |
0120145 |
00120012010120120120120145201204 |
375 |
406 |
8875 |
0102010302 |
010200101020110102010301020102010302 |
594 |
719 |
14437 |
0102010302 |
02010103001010201030201 |
266 |
312 |
9453 |
abcdaef |
abcdaefarqvzv |
63 |
47 |
2515 |
01 |
010203 |
31 |
16 |
656 |
001 |
0101010101010101010101010100101010101 |
204 |
312 |
6359 |
0000000001 |
0000000010000000010000000001000000001 |
875 |
735 |
8031 |
4.4. Анализ полученных результатов
Как видно из приведённых выше результатов тестов, метод поиска подстроки с помощью конечного автомата является неэффективным и по неизвестным причинам, вопреки теоретическим ожиданиям, работает в большинстве случаев более чем в 10 раз медленнее линейного поиска.
Следовательно, несмотря на теоретическую изящность и асимптотическую оптимальность, метод не может быть применён на практике.
В качестве предположительных причин подобной ситуации можно назвать:
ВЫВОДЫ
При выполнении курсового проекта для достижения поставленной цели был проведен анализ алгоритмов, в результате которого была выявлена сложность и детали реализации алгоритмов.
Результатом анализа алгоритмов стал программный продукт, реализующий поиск подстроки в множество строк с помощью конечного автомата.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Н. Вирт, Алгоритмы и структуры данных
2. Д. Кнут, Искусство программирования
Приложение А
Техническое задание
А.1 Общие сведения
Полное наименование создаваемого программного продукта: «Поиск подстроки с помощью конечного автомата».
Программный продукт проектируется студентом группы ПОС-12а Ольмезовым Константином Ивановичем.
Основанием для создания программного продукта является задание, выданное кафедрой программного обеспечения интеллектуальных систем.
Плановый срок начала работы по созданию программного продукта: 09 сентября 2013 года и срок окончания: 12 декабря 2013 года.
А.2 Назначение и цели создания программы
Программа предназначена для автоматизации процесса построения функции «поиск подстроки в строке с помощью конечного автомата» и работы с ней.
Основной целью проекта является программная реализация алгоритма построения функции «поиск подстроки в строке с помощью конечного автомата».
А.3 Характеристика объекта автоматизации
А.3.1 Сведения об объекте автоматизации
Объектом автоматизации является процесс организации поиска подстроки в строке с помощью конечных автоматов.
А.3.2 Сведения об условиях эксплуатации программного продукта
Проектируемая программа может быть использована учащимися и студентами для построения конечного автомата для поиска на основе заданной подстроки, для поиска подстроки в строке по данному автомату.
А.4 Требования к программному продукту
А.4.1 Требования к ПП в целом
В целом к программному продукту предъявляются следующие требования:
А.4.2 Требования к задачам и функциям, выполняемым программой
Система должна обеспечивать решение таких задач:
А.4.3 Требования к видам обеспечения
А.4.3.1 Требования к техническому обеспечению
Для нормального функционирования проектируемого продукта:
А.4.3.2 Требования к информационному обеспечению
Информационная модель должна включать в себя организацию структуры данных для хранения данной структуры данных в памяти (в оперативной памяти и в файле);
А.4.3.3 Требования к программному обеспечению
Программный продукт создается для операционной системы Windows XP, Windows 7, Windows 8/8.1. Разработка проекта предусматривается на языке C++.
А.4.3.4 Требования к организационному обеспечению
В программную документацию должны входить:
а) техническое задание;
б) листинги основных блоков программы;
в) руководство пользователя;
г) экранные формы.
Таблица А.1 - Стадии и этапы разработки программного продукта
Этапы работы |
Срок выполнения |
1 Постановка задачи (определений требований к ПП, формулировка постановки задачи: исходные данные, ограничения, результаты, связь). |
1-2 недели |
2 Составление технического задания. |
2-я неделя |
3 Сбор и изучение информации по заданному алгоритму. |
3-я неделя |
4 Техническое проектирование (разработка методов решения задачи и модульный анализ: определение структуры программы, выделение модулей, организация или взаимосвязи). |
4-5 недели |
5 Рабочее программирование: определение структур входных и выходных данных, алгоритмов работы модулей, оценки структур данных и алгоритмов, описание входных и выходных данных. |
6-я неделя |
6 Разработка самого алгоритма функционирования программы, составление спецификаций модулей. |
7 неделя |
7 Написание программы:
|
8-10 недели 11-12 недели 12-13 недели 11-14 недели |
8 Защита курсового проекта. |
14-16 недели |
Приложение Б
Основное меню состоит из нескольких пунктов:
Рисунок B.1 вид главного меню программы
Рисунок B.2 панель ввода подстроки
Рисунок B.3 панель исследования алгоритма
Рисунок B.4 наглядный поиск подстроки с отображением автомата
Рисунок B.5 отображение автомата программой
Приложение Г
ЛИСТИНГ ПРОГРАММЫ
Г1. Файл AutomatFunctions.h
typedef map<char,int> automat_state;
typedef vector<automat_state> automat;
//Поиск z-функции строки
vector<int> get_z_function(char *t,int N)
{
vector<int> z(N,0);
int l=0,r=0;
for (int i=1;i<N;i++)
{
if (i<r)
z[i]=min(z[i-l],r-i+1);
while (i+z[i]<N && t[z[i]]==t[i+z[i]])
z[i]++;
if (i+z[i]>r)
{
l=i;
r=i+z[i]-1;
}
}
return z;
}
void build_automat(char *substr,automat &machine)
{
int i,j;
int len=strlen(substr);
automat_state::iterator search;
vector<int> z=get_z_function(substr,len);
//machine - автомат
//Автомат хранится как вектор множеств
//Каждый элемент вектора - состояние автомата
//Множество каждого вектора хранит в себе пары -
//символ и номер состояния, в которое ведёт
//переход по этому символу
machine.assign(len+1,automat_state());
//Добавляем самые очевидные переходы -
//от символа к следующему по всей строк
machine[0][substr[0]]=1;
for (i=1;i<len;i++)
machine[i][substr[i]]=i+1;
//Зацикливание на первом символе
if (substr[0]!=substr[1])//Только если первые два символа не повторяются
machine[1][substr[0]]=1;
for (i=1;i<len;i++)
{
for (j=0;j<=z[i];j++)//Переходим по всем символам совпадающего префикса
{
if (!machine[i+j].count(substr[j]))
machine[i+j][substr[j]]=j+1;
}
}
}
int automat_search_substring(char *str,automat &machine,char *substr)
{
int i;
int len=machine.size()-1;
int now_state=0;
char *now=str;
char c;
while (*now)
{
if (machine[now_state].count(*now))
now_state=machine[now_state][*now];
else
now_state=0;
//now_state=machine[now_state][*now];
if (now_state==len)
return now-len-str+1;
++now;
}
return 0;
}
Г2. Файл Unit1.h
//---------------------------------------------------------------------------
#ifndef Unit1H
#define Unit1H
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
TPanel *InputSubstringPanel;
TEdit *KeyboardInputSubstringText;
TButton *KeyboarInputSubstringButton;
TEdit *FileInputSubstringText;
TButton *FileInputSubstringButton;
TLabel *Label1;
TLabel *InputSubstringError;
TPanel *InputStringPanel;
TLabel *Label2;
TLabel *InputStringError;
TEdit *KeyboardInputStringText;
TButton *KeyboardInputStringButton;
TEdit *FileInputStringText;
TButton *FileInputStringButton;
TPanel *MainMenuPanel;
TLabel *Label3;
TButton *MainMenuInputSubstringButton;
TButton *MainMenuInputStringButton;
TButton *MainMenuStudyAlgorithmButton;
TButton *MainMenuVisualSearchButton;
TButton *MainMenuShowAutomat;
TButton *MainMenuByMethodButton;
TButton *MainMenuByProgramButton;
TButton *MainMenuExitButton;
TButton *InputStringCancelButton;
TButton *InputSubstringCancelButton;
TPanel *ShowAutomatPanel;
TPaintBox *ShowAutomatPaintBox;
TButton *ShowAutomatCancelButton;
TPanel *StudyAlgorithmPanel;
TLabel *StudySubstringLabel;
TLabel *StudyStringLabel;
TButton *StudyButton;
TLabel *StudyInfoLabel;
TPanel *VisualSearchPanel;
TPaintBox *VisualSearchAutomatPaintBox;
TButton *VisualSearchCancelButton;
TButton *VisualSearchGoButton;
TPaintBox *VisualSearchStringPaintBox;
TButton *StudyAlgorithmCancelButton;
TPanel *MethodInfoPanel;
TLabel *MethodInfoLabel;
TButton *MethodInfoCancelButton;
TButton *MethodInfoNextPageButton;
TButton *MethodInfoPrevPageButton;
TPanel *ProgramInfoPanel;
TLabel *ProgramInfoLabel;
TButton *ProgramInfoCancelButton;
void __fastcall KeyboarInputSubstringButtonClick(TObject *Sender);
void __fastcall FileInputSubstringButtonClick(TObject *Sender);
void __fastcall KeyboarInputStringButtonClick(TObject *Sender);
void __fastcall FileInputStringButtonClick(TObject *Sender);
void __fastcall MainMenuInputSubstringButtonClick(TObject *Sender);
void __fastcall BeginWork();
void __fastcall InputSubstringCancelButtonClick(TObject *Sender);
void __fastcall InputStringCancelButtonClick(TObject *Sender);
void __fastcall MainMenuInputStringButtonClick(TObject *Sender);
void __fastcall ShowAutomatCancelButtonClick(TObject *Sender);
void __fastcall MainMenuShowAutomatClick(TObject *Sender);
void __fastcall ShowAutomatPaintBoxPaint(TObject *Sender);
void __fastcall MainMenuExitButtonClick(TObject *Sender);
void __fastcall MainMenuStudyAlgorithmButtonClick(TObject *Sender);
void __fastcall StudyButtonClick(TObject *Sender);
void __fastcall VisualSearchCancelButtonClick(TObject *Sender);
void __fastcall MainMenuVisualSearchButtonClick(TObject *Sender);
void __fastcall VisualSearchAutomatPaintBoxClick(TObject *Sender);
void __fastcall VisualSearchStringPaintBoxPaint(TObject *Sender);
void __fastcall VisualSearchGoButtonClick(TObject *Sender);
void __fastcall StudyAlgorithmCancelButtonClick(TObject *Sender);
void __fastcall MainMenuByMethodButtonClick(TObject *Sender);
void __fastcall MethodInfoNextPageButtonClick(TObject *Sender);
void __fastcall MethodInfoPrevPageButtonClick(TObject *Sender);
void __fastcall MethodInfoCancelButtonClick(TObject *Sender);
void __fastcall MainMenuByProgramButtonClick(TObject *Sender);
void __fastcall ProgramInfoCancelButtonClick(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
Г3. Файл Unit1.cpp
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
#include <Windows.h>
#include <stdio.h>
#include <time.h>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <stdlib.h>
using namespace std;
#include "AutomatFunctions.h"
TForm1 *Form1;
//AnsiString str="abvdsweertyygvedrszbresvzemkmzokcosef",substr="0102x0103abc";
AnsiString str="010200101020110102010301020102010302",substr="0102010302";
automat machine;
bool begin_work=false;
const int COUNT_PAGE_METHOD_INFO=4;
int now_method_info_page=1;
AnsiString MethodInfo[]=
{
"Метод конечных автоматов позволяет определить вхождение подстроки \
за один проход по строке (линейное время, пропорционально длине \
строки). При этом препроцессинг (построение автомата) требует \
квадратичного времени (пропорционального квадрату длины подстроки).",
"Количество состояний автомата равно количеству символов в подстроке \
плюс одно начальное. Входной алфавит автомата - строка, где производится \
поиск. Нахождение автомата в i-том состоянии означает, что i символов \
справа от текущей позиции строки являются префиксом подстроки.",
"Очевидно, что в автомате будет присутствовать переходы из i-того в \
(i+1)-ое состояние по i-тому символу строки (индексация с нуля). Главную \
сложность представляет необходимость учитывать повторение префиксов в \
строке. Например, переход из третьего состояния по символу 'b' в строке \
\"abac\"",
"При выполнении всех вышеописанных условий можно будет подавать строку на \
вход построенному автомату. В позиции, где автомат достигает конечного \
состояния, находится конец вхождения подстроки."
};
//Функция отрисовки автомата на Canvas-е
void ShowAutomat(TPaintBox *Box,int now_state,char c='\0')
{
const int BeginX=10,BeginY=10;
const int StateWidth=40,StateHeight=70;
const int TextInterval=5;
const int TextLineInterval=15;
const int HorizInterval=0,VertInterval=30;
const int CircleRadius=30;
const int Width=11;
int i;
int x;
bool f;
automat_state::iterator I;
int X=BeginX,Y=BeginY;
Box->Canvas->Brush->Color=clMedGray;
#include <Windows.h>
PatBlt(Box->Canvas->Handle,0,0,
Box->Width,Box->Height, clWhite);
for (i=0,x=0;i<machine.size();i++)
{
//Прорисовка круга
TRect TR(X+(StateWidth-CircleRadius)/2,
Y,X+(StateWidth+CircleRadius)/2,
Y+CircleRadius);
AnsiString text;
Box->Canvas->Brush->Color=clMedGray;
if (i==now_state)
Box->Canvas->Brush->Style=bsSolid;
else
Box->Canvas->Brush->Style=bsClear;
Box->Canvas->Ellipse(TR.Left,TR.Top,TR.Right,TR.Bottom);
//Прорисовка символа
Box->Canvas->Brush->Style=bsClear;
Box->Canvas->Font->Color=clBlack;
if (i<machine.size()-1)
text=IntToStr(i);
else
text="";
Box->Canvas->TextRect(TR,TR.Left+CircleRadius/2-6,
TR.Top+CircleRadius/2-7,text);
//Прорисовка переходов
if (i<machine.size()-1)//Только не для конечного состояния
{
int LineY=TR.Bottom+TextInterval;
f=false;
for (I=machine[i].begin();I!=machine[i].end();++I)
{
if (i==now_state && I->first==c)
{
Box->Canvas->Font->Color=clRed;
f=true;
}
else
{
Box->Canvas->Font->Color=clBlack;
}
if (I->second<machine.size()-1)
Box->Canvas->TextOut(TR.Left,
LineY,"'"+AnsiString(I->first)+"'->"+IntToStr(I->second));
else
Box->Canvas->TextOut(TR.Left,
LineY,"'"+AnsiString(I->first)+"'->[K]");
LineY+=TextLineInterval;
}
if (!f && c!='\0' && i==now_state)
{
Box->Canvas->Font->Color=clRed;
Box->Canvas->TextOut(TR.Left,
LineY,"to 0");
}
}
X+=StateWidth+HorizInterval;
++x;
if (x==Width)
{
X=BeginX;
Y+=StateHeight+VertInterval;
}
}
}
//Функция отрисовки строки на Canvas-е
void ShowString(TPaintBox *Box,int now_pos,int L=1)
{
const int BeginX=0,BeginY=0;
const int HorizInterval=10;
char *arr=str.c_str();
int len=str.Length();
int i;
Box->Canvas->Font->Name="Courier";
Box->Canvas->Font->Color=clBlack;
for (i=0;i<len;i++)
{
if (i>=now_pos && i<now_pos+L)
Box->Canvas->Font->Color=clRed;
else if (i==now_pos+L)
Box->Canvas->Font->Color=clBlack;
Box->Canvas->TextOut(BeginX+i*HorizInterval,BeginY,
AnsiString(arr[i]));
}
}
void SetMethodInfoPage(int page)
{
now_method_info_page=page;
Form1->MethodInfoLabel->Caption=MethodInfo[now_method_info_page];
Form1->MethodInfoPrevPageButton->Visible=(now_method_info_page!=0);
Form1->MethodInfoNextPageButton->Visible=
(now_method_info_page!=COUNT_PAGE_METHOD_INFO-1);
}
void InitPanel(TPanel *P)
{
P->Left=1;
P->Top=1;
P->Visible=false;
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
InitPanel(MainMenuPanel);
InitPanel(InputSubstringPanel);
InitPanel(InputStringPanel);
InitPanel(ShowAutomatPanel);
InitPanel(StudyAlgorithmPanel);
InitPanel(VisualSearchPanel);
InitPanel(MethodInfoPanel);
InitPanel(ProgramInfoPanel);
MainMenuPanel->Visible=true;
build_automat(substr.c_str(),machine);
InputSubstringCancelButton->Visible=false;
InputStringCancelButton->Visible=false;
ProgramInfoLabel->Caption =
"Программа является курсовым проектом студента 2 курса\n\
ДонНТУ (КНТ, ПОС-12а)\n\
Ольмезова Константина Ивановича\n\
© 2014";
}
void __fastcall TForm1::BeginWork()
{
begin_work=true;
InputSubstringCancelButton->Visible=true;
InputStringCancelButton->Visible=true;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::KeyboarInputSubstringButtonClick(TObject *Sender)
{
if (KeyboardInputSubstringText->Text.Length()==0)
{
InputSubstringError->Caption="Введена пустая строка!";
return;
}
substr=KeyboardInputSubstringText->Text;
build_automat(substr.c_str(),machine);
InputSubstringPanel->Visible=false;
if (!begin_work)
{
InputStringPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат - ввод строки";
}
else
{
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
StudyInfoLabel->Caption="";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FileInputSubstringButtonClick(TObject *Sender)
{
if (FileInputSubstringText->Text.Length()==0)
{
InputSubstringError->Caption="Пустое имя файла!";
return;
}
FILE *F=fopen(FileInputSubstringText->Text.c_str(),"rt");
if (!F)
{
InputSubstringError->Caption="Чтение из файла невозможно!";
return;
}
char t[1024];
fscanf(F,"%s",t);
substr=t;
fclose(F);
build_automat(substr.c_str(),machine);
InputSubstringPanel->Visible=false;
if (!begin_work)
{
InputStringPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат - ввод строки";
}
else
{
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
StudyInfoLabel->Caption="";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::KeyboarInputStringButtonClick(TObject *Sender)
{
if (KeyboardInputStringText->Text.Length()==0)
{
InputStringError->Caption="Введена пустая строка!";
return;
}
str=KeyboardInputStringText->Text;
InputStringPanel->Visible=false;
MainMenuPanel->Visible=true;
StudyInfoLabel->Caption="";
Form1->Caption="Поиск подстроки через автомат";
BeginWork();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FileInputStringButtonClick(TObject *Sender)
{
if (FileInputStringText->Text.Length()==0)
{
InputStringError->Caption="Пустое имя файла!";
return;
}
FILE *F=fopen(FileInputStringText->Text.c_str(),"rt");
if (!F)
{
InputStringError->Caption="Чтение из файла невозможно!";
return;
}
char t[1024];
fscanf(F,"%s",t);
str=t;
fclose(F);
InputStringPanel->Visible=false;
MainMenuPanel->Visible=true;
StudyInfoLabel->Caption="";
Form1->Caption="Поиск подстроки через автомат";
BeginWork();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuInputSubstringButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
InputSubstringPanel->Visible=true;
InputSubstringError->Caption="";
KeyboardInputSubstringText->Text=substr;
FileInputSubstringText->Text="";
Form1->Caption="Поиск подстроки через автомат - ввод подстроки";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::InputSubstringCancelButtonClick(TObject *Sender)
{
InputSubstringPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::InputStringCancelButtonClick(TObject *Sender)
{
InputStringPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuInputStringButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
InputStringPanel->Visible=true;
InputStringError->Caption="";
KeyboardInputStringText->Text=str;
FileInputStringText->Text="";
Form1->Caption="Поиск подстроки через автомат - ввод строки";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ShowAutomatCancelButtonClick(TObject *Sender)
{
ShowAutomatPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuShowAutomatClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
ShowAutomatPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат - отображение автомата";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ShowAutomatPaintBoxPaint(TObject *Sender)
{
ShowAutomat(ShowAutomatPaintBox,machine.size());
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuExitButtonClick(TObject *Sender)
{
Form1->Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuStudyAlgorithmButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
StudyAlgorithmPanel->Visible=true;
StudySubstringLabel->Caption="Substring: "+substr;
StudyStringLabel->Caption="String: "+str;
Form1->Caption="Поиск подстроки через автомат - исследование алгоритма";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::StudyButtonClick(TObject *Sender)
{
const int COUNT=1000000;
int i,j,q;
DWORD begin,time;
int pos;
char *str_arr,*sub_arr;
int str_len=str.Length(),sub_len=substr.Length();
str_arr=str.c_str();
sub_arr=substr.c_str();
AnsiString text=IntToStr(COUNT)+" run search\n================\n";
begin=GetTickCount();
for (q=0;q<COUNT;q++)
pos=strstr(str_arr,sub_arr)-str_arr;
time=GetTickCount()-begin;
text+="Standart search time: "+IntToStr(time)+"\n";
StudyInfoLabel->Caption=text;
begin=GetTickCount();
for (q=0;q<COUNT;q++)
{
pos=0;
for (i=0;i<=str_len-sub_len;i++)
{
for (j=0;j<sub_len;j++)
if (str_arr[i+j]!=sub_arr[j])
break;
if (j==sub_len)
{
pos=i+1;
break;
}
}
}
time=GetTickCount()-begin;
text+="Linear search time: "+IntToStr(time)+"\n";
StudyInfoLabel->Caption=text;
begin=GetTickCount();
for (q=0;q<COUNT;q++)
pos=automat_search_substring(str_arr,machine,sub_arr);
time=GetTickCount()-begin;
text+="Automat search time: "+IntToStr(time)+"\n";
StudyInfoLabel->Caption=text;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::VisualSearchCancelButtonClick(TObject *Sender)
{
VisualSearchPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuVisualSearchButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
VisualSearchPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат - наглядный поиск";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::VisualSearchAutomatPaintBoxClick(TObject *Sender)
{
ShowAutomat(VisualSearchAutomatPaintBox,machine.size());
}
//---------------------------------------------------------------------------
void __fastcall TForm1::VisualSearchStringPaintBoxPaint(TObject *Sender)
{
ShowString(VisualSearchStringPaintBox,str.Length());
}
//---------------------------------------------------------------------------
void __fastcall TForm1::VisualSearchGoButtonClick(TObject *Sender)
{
int i;
int now=0;
int len=str.Length();
char *arr=str.c_str();
ShowString(VisualSearchStringPaintBox,-1);
ShowAutomat(VisualSearchAutomatPaintBox,now);
for (i=0;i<len;i++)
{
Sleep(300);
ShowString(VisualSearchStringPaintBox,i);
Sleep(300);
ShowAutomat(VisualSearchAutomatPaintBox,now,*arr);
if (machine[now].count(*arr))
now=machine[now][*arr];
else
now=0;
Sleep(300);
ShowString(VisualSearchStringPaintBox,-1);
ShowAutomat(VisualSearchAutomatPaintBox,now);
++arr;
if (now==machine.size()-1)
break;
}
if (i!=len)
{
ShowString(VisualSearchStringPaintBox,
i-substr.Length()+1,substr.Length());
}
else
{
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::StudyAlgorithmCancelButtonClick(TObject *Sender)
{
StudyAlgorithmPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuByMethodButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
MethodInfoPanel->Visible=true;
SetMethodInfoPage(0);
Form1->Caption="Поиск подстроки через автомат - о методе";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MethodInfoNextPageButtonClick(TObject *Sender)
{
SetMethodInfoPage(++now_method_info_page);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MethodInfoPrevPageButtonClick(TObject *Sender)
{
SetMethodInfoPage(--now_method_info_page);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MethodInfoCancelButtonClick(TObject *Sender)
{
MethodInfoPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::MainMenuByProgramButtonClick(TObject *Sender)
{
MainMenuPanel->Visible=false;
ProgramInfoPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат - о программе";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ProgramInfoCancelButtonClick(TObject *Sender)
{
ProgramInfoPanel->Visible=false;
MainMenuPanel->Visible=true;
Form1->Caption="Поиск подстроки через автомат";
}
//---------------------------------------------------------------------------