Разработка комплекса программ и реализация алгоритмов поиска подстроки

http://www.r

Курсовая работа Разработка комплекса программ и реализация алгоритмов поиска подстроки Пояснительная записка Пояснительная записка содержит 37 страниц, 7 рисунков, 1 таблицу, 4 источника, 2 приложения.

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

В процессе разработки на базе анализа проблемы проведено обоснование и выбор средств разработки программного комплекса.

В результате разработана структура, программного комплекса, класс абстрактного типа данных — список (далее АТД — список). На программном уровне комплекс реализован на языке С++ в среде разработки Visual Studio.

При разработке программного комплекса была использована современная технология объектно-ориентированного программирования и проектирования графического пользовательского интерфейса, такая, как Windows Forms.

Введение

Постановка задачи

Описание структуры данных

Разработка детальных алгоритмов решения

Разработка структуры программы

Описание программы

Экспериментальная часть

Заключение

Список литературы

Приложение А. Графическая часть

Приложение Б. Исходный код программы

Введение

В процессе выполнения курсового проекта должен быть реализован комплекс программ поиска подстроки в тексте алгоритмом прямого поиска и алгоритмом Кнута-Морриса-Пратта. Должен быть разработан АТД или с представлением описания. Должна быть разработана программа тестирования трудоёмкости операций. Эффективность работы алгоритмов должна быть представлена на графиках. Должен быть выполнен сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов. Работа алгоритмов должна быть представлена скриншотами интерфейса программы. ПО должно быть разработано на языке программирования С++.

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

В настоящее время функции поиска подстроки в строке инкапсулированы во многие высокоуровневые языки программирования. Но стоит помнить, что стандартные функции далеко не самые оптимальные и эффективные, и если основной задачей программы является нахождение подстроки в строке, то необходимо знать принципы организации функций поиска. Также не нужно забывать, что область применения функций поиска не ограничивается одними текстовыми редакторами и базами данных. Алгоритмы поиска используются различными поисковыми роботами при индексации страниц, и от скорости нахождения необходимых ключевых слов в тексте зависит актуальность информации. Спам-фильтр почтовых сервисов также занимается поиском в тексте писем определенных фраз. Все это говорит об актуальности проблемы поиска подстроки в строке.

Описание структуры данных.

АТД — массив структур struct line, содержит int id — идентификатор строки, char str[255] - строка. line *arr — указатель на сам массив. Массив сразу создаётся с размером n = 0. Размер n изменяется при последующем добавлении элементов. АТД — список имеет компонентные функции: загрузка данных из файла, добавление элемента, удаление элемента. Вызов функций АТД реализован в пользовательском интерфейсе программы. Исходный код АТД см. приложение 1.

Данные:

Параметры:

int id — идентификатор элемента массива структур;

char str[255] - строка.

Структура данных:

Массив структур размером n.

Операции:

Загрузка из файла:

Вход: имя файла с входными данными wchar_t file[255];

Процесс: формирование массива из файла;

Выход: новый размер списка n;

Добавить строку:

Вход: String^ str — строка для добавления;

Процесс: включение полученной строки в массив, выполняется функцией Addline ();

Выход: новый размер массива n+1;

Удалить строку:

Вход: int number — идентификатор удаляемой строки;

Процесс: поиск идентификатора строки и присваивание ему значения -10;

Выход: новый размер size-1;

Удаление массива структур:

Процесс: удаление массива структур;

Конец АТД.

Разработка детальных алгоритмов решения Алгоритм прямого поиска подстроки.

Пусть заданы массивы символов типа char: строка S как размером N, подстрока P размером M (см. блок 2). Поиск завершается после поиска подстроки P во всех строках S, это позволяет получить результат о всех найденных вхождениях P в S. Поиск считается удачным, если количество совпавших символов будет равно длине подстроки (см. блоки 7−9). Алгоритм содержит условие, предотвращающее выход за пределы строки (см. блок 10). Проход по каждому символу строки осуществляется счетчиками (см. блок 4, блок 6).

Алгоритм Кнута-Морриса-Пратта.

В этом алгоритме подстрока (образ) размером N сравнивается со строкой S размером M и если встречается несовпадение, следующее сравнение начинается с первой несовпадающей позиции в строке. Если совпадения вообще нет, то сравнение начинается со следующей позиции в строке.

Для работы алгоритма вводится дополнительный массив для вычисления сдвига на очередном шаге — D. Этот массив может быть получен на основе анализа образа Р и зависит только от содержимого подстроки. До начала самого поиска подстроки в строке можно вычислить значения сдвигов, которые используются в дальнейшем поиске. Причем в массив D помещается значение = -1, если производится сдвиг на целый образ. Чем меньше значение D, тем на большее число позиций производится сдвиг по строке. Сдвиг для ячейки j вычисляется как j-d[j]. Основным отличием КМП-алгоритма от алгоритма прямого поиска является осуществления сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

Блок схемы алгоритмов представлены см. приложение А.

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

Разработанная программа состоит из 4 основных функций:

void ShowStruct () — функция вывода массива на экран;

int LineFind (array^ fstr, int m) — функция прямого поиска подстроки. Вход: искомая подстрока, размер искомой строки.

Выход: Возвращает 1 если поиск успешен, 0 — если не успешен.

int algorithm_KMP (array^ fstr, int l) — функция поиска алгоритма Бойера-Мура. Вход: искомая подстрока, адрес строки в массиве строк. Выход: возвращает адрес строки.

int Addline () — функция добавления строки в массив структур. Выход: возвращает 1 — если добавление успешно, 0 — если добавление неудачно.

Помимо основных функций АТД в программе присутствуют функции обработки нажатий на кнопки:

private:System:Void Form1_Load (System:Object^sender, System: EventArgs^ e) — функция открытия формы.

private: System: Void button1_Click (System:Object^ sender, System: EventArgs^ e) — функция поиска.

private: System: Void button2_Click (System:Object^ sender, System: EventArgs^ e) — функция загрузки из файла массива структур.

private: System: Void button3_Click (System:Object^ sender, System: EventArgs^ e) — функция удаления массива структур и закрытия формы.

private:System:Void button4_Click (System:Object^ sender, System: EventArgs^ e) — функция добавления строки в массив структур.

private:System:Void button5_Click (System:Object^ sender, System: EventArgs^ e) — функция удаления строки из массива структур.

private:System:Void очиститьМассивСтруктурToolStripMenuItem_Click (System:Object^ sender, System: EventArgs^ e) — функция очищения всех полей и удаления массива структур.

private:System:Void открытьToolStripMenuItem_Click (System:Object^ sender, System: EventArgs^ e) — функция выбора файла для чтения.

Структурная схема программы представлена в приложении А. Исходный код см. приложение Б.

Описание программы.

В программе реализована возможность загрузки текста из файла или вручную. Помимо этого также реализована функция удаления строки. Из полученных данных формируется массив структур, размер которого в дальнейшем может быть изменен пользователем посредством функций добавления и удаления строки. Результатом работы программы являются координаты найденной подстроки в тексте и время поиска, выведенные в специальные поля. Результаты работы программы выводятся на экран, см. Рис4−5.

Работа алгоритмов представлена скриншотами.

Для заполнения списка строками можно воспользоваться возможностью загрузки текста из файла: для начала нужно выбрать файл (Файл — открыть) см. Рис1.

Рис1. Пример выбора файла Рис2. Добавление строки Затем заполнить массив структур с помощью кнопки «Заполнить массив». Присутствует возможность ввести строки вручную используя кнопку «Добавить строку». Кнопка добавления также предоставляет пользователю возможность добавить строку к загруженному из файла тексту, см. Рис2.

Кнопка «Удалить строку» реализует возможность удаления строки из текста, см. Рис3.

Рис3. Удаление строки Рис4. Поиск и вывод результатов работы.

Рис5.Поиск и вывод результатов работы Экспериментальная часть Исследование эффективности алгоритмов Тестирование программы проводилось на входных данных различного размера. В качестве входной информации были использованы текстовые файлы содержащие английский текст. Зависимость времени поиска от размера для каждого алгоритма представлено в Таблице 1 и Рис 6.

Таблица1.

Рис 6. График зависимости времени от кол-ва символов.

Анализируя график Рис 6 и Таблицу 1 можно утверждать, что алгоритм КМП дает выигрыш в тех случаях, когда несовпадению предшествует некоторое число совпадений, так как в этом случае образ сдвигается сразу на несколько позиций. Но это бывает не так часто, поэтому выигрыш, по сравнению с прямым поиском, не всегда значителен Исследование трудоёмкости.

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

Рис 7. Зависимость трудоемкости от размера.

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

Заключение

В результате написания курсового проекта мною были разработаны и реализованы: алгоритмы поиска подстроки в тексте, АТД — массив структур, программа тестирования трудоёмкости для алгоритма прямого поиска. После чего, были приведены график эффективности алгоритмов поиска и график зависимости трудоёмкости прямого поиска от размера текста. Также пояснительная записка содержит описание АТД — список и структуры программы. Работоспособность программы показана на рисунках. Комплекс программ разработан на языке программирования С++ в среде Visual Studio.

В разработанной программе реализованы следующие возможности:

Формирование массива строк из файла;

Добавление строки в массив;

Удаление строки из массива;

Очистка массива;

Прямой поиск;

Поиск алгоритмом Кнута-Морриса-Пратта;

Вывод результатов работы программы в отдельное поле.

1. Д. Макконнел. Основы современных алгоритмов. М.: Техносфера, 2010. 368 с.

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

3. Р. Седжвик. Фундаментальные алгоритмы C++. Части 1−4. М.: Диасофт,

ПРИЛОЖЕНИЕ, А ПРИЛОЖЕНИЕ Б

#pragma once

#include

#include

#include

#include

#include

#include

#include

#include

namespace KursachSia_Kod {

using namespace System;

using namespace System: Runtime:InteropServices;

using namespace System: ComponentModel;

using namespace System: Collections;

using namespace System: Windows:Forms;

using namespace System: Data;

using namespace System: Drawing;

using namespace System: IO;

using namespace std;

struct line

{

char str[255];

int id;

};

line *arr;

int n=-1,m=0,choice=0,longstr=0,kol=0;

wchar_t file[255];

/// Сводка для Form1

public ref class Form1: public System: Windows:Forms:Form

{

public:

Form1(void)

{

InitializeComponent ();

//TODO: добавьте код конструктора

}

protected:

/// Освободить все используемые ресурсы.

~Form1()

{

if (components)

{

delete components;

}

}

private: System: Windows:Forms:RadioButton^ radioButton1;

protected:

private: System: Windows:Forms:RadioButton^ radioButton2;

private: System: Windows:Forms:TextBox^ textBox1;

private: System: Windows:Forms:TextBox^ textBox2;

private: System: Windows:Forms:Button^ button1;

private: System: Windows:Forms:TextBox^ textBox3;

private:

private:

private: System: Windows:Forms:Label^ label1;

private: System: Windows:Forms:Label^ label2;

private: System: Windows:Forms:Label^ label3;

private: System: Windows:Forms:Button^ button2;

private: System: Windows:Forms:Button^ button3;

private: System: Windows:Forms:Label^ label6;

private: System: Windows:Forms:Label^ label4;

private: System: Windows:Forms:ToolTip^ toolTip1;

private: System: Windows:Forms:Button^ button4;

private: System: Windows:Forms:TextBox^ textBox4;

private: System: Windows:Forms:Button^ button5;

private: System: Windows:Forms:TextBox^ textBox5;

private: System: Windows:Forms:Label^ label7;

private: System: Windows:Forms:Label^ label8;

private: System: Windows:Forms:MenuStrip^ menuStrip1;

private: System: Windows:Forms:ToolStripMenuItem^ файлToolStripMenuItem;

private: System: Windows:Forms:ToolStripMenuItem^ открытьToolStripMenuItem;

private: System: Windows:Forms:ToolStripMenuItem^ очиститьМассивСтруктурToolStripMenuItem;

private: System: Windows:Forms:OpenFileDialog^ openFileDialog1;

private: System: ComponentModel:IContainer^ components;

private:

/// Требуется переменная конструктора.

#pragma region Windows Form Designer generated code

/// Обязательный метод для поддержки конструктора — не изменяйте

/// содержимое данного метода при помощи редактора кода.

void InitializeComponent (void)

{

this->components = (gcnew System: ComponentModel:Container ());

this->radioButton1 = (gcnew System: Windows:Forms:RadioButton ());

this->radioButton2 = (gcnew System: Windows:Forms:RadioButton ());

this->textBox1 = (gcnew System: Windows:Forms:TextBox ());

this->textBox2 = (gcnew System: Windows:Forms:TextBox ());

this->button1 = (gcnew System: Windows:Forms:Button ());

this->textBox3 = (gcnew System: Windows:Forms:TextBox ());

this->label1 = (gcnew System: Windows:Forms:Label ());

this->label2 = (gcnew System: Windows:Forms:Label ());

this->label3 = (gcnew System: Windows:Forms:Label ());

this->button2 = (gcnew System: Windows:Forms:Button ());

this->button3 = (gcnew System: Windows:Forms:Button ());

this->label6 = (gcnew System: Windows:Forms:Label ());

this->label4 = (gcnew System: Windows:Forms:Label ());

this->toolTip1 = (gcnew System: Windows:Forms:ToolTip (this->components));

this->button4 = (gcnew System: Windows:Forms:Button ());

this->textBox4 = (gcnew System: Windows:Forms:TextBox ());

this->button5 = (gcnew System: Windows:Forms:Button ());

this->textBox5 = (gcnew System: Windows:Forms:TextBox ());

this->label7 = (gcnew System: Windows:Forms:Label ());

this->label8 = (gcnew System: Windows:Forms:Label ());

this->menuStrip1 = (gcnew System: Windows:Forms:MenuStrip ());

this->файлToolStripMenuItem = (gcnew System: Windows:Forms:ToolStripMenuItem ());

this->открытьToolStripMenuItem = (gcnew System: Windows:Forms:ToolStripMenuItem ());

this->очиститьМассивСтруктурToolStripMenuItem = (gcnew System: Windows:Forms:ToolStripMenuItem ());

this->openFileDialog1 = (gcnew System: Windows:Forms:OpenFileDialog ());

this->menuStrip1->SuspendLayout ();

this->SuspendLayout ();

// radioButton1

this->radioButton1->AutoSize = true;

this->radioButton1->Location = System: Drawing:Point (235, 28);

this->radioButton1->Name = L" radioButton1″ ;

this->radioButton1->Size = System: Drawing:Size (201, 17);

this->radioButton1->TabIndex = 0;

this->radioButton1->TabStop = true;

this->radioButton1->Text = L" Прямой поиск подстроки в строке" ;

this->radioButton1->UseVisualStyleBackColor = true;

this->radioButton1->CheckedChanged += gcnew System: EventHandler (this, &Form1:radioButton1_CheckedChanged);

// radioButton2

this->radioButton2->AutoSize = true;

this->radioButton2->Location = System: Drawing:Point (235, 61);

this->radioButton2->Name = L" radioButton2″ ;

this->radioButton2->Size = System: Drawing:Size (101, 17);

this->radioButton2->TabIndex = 1;

this->radioButton2->TabStop = true;

this->radioButton2->Text = L" Алгоритм КМП" ;

this->radioButton2->UseVisualStyleBackColor = true;

this->radioButton2->CheckedChanged += gcnew System: EventHandler (this, &Form1:radioButton2_CheckedChanged);

// textBox1

this->textBox1->Location = System: Drawing:Point (12, 41);

this->textBox1->Multiline = true;

this->textBox1->Name = L" textBox1″ ;

this->textBox1->ScrollBars = System: Windows:Forms:ScrollBars:Both;

this->textBox1->Size = System: Drawing:Size (195, 235);

this->textBox1->TabIndex = 2;

this->textBox1->TextChanged += gcnew System: EventHandler (this, &Form1:textBox1_TextChanged);

// textBox2

this->textBox2->Location = System: Drawing:Point (272, 124);

this->textBox2->Name = L" textBox2″ ;

this->textBox2->ScrollBars = System: Windows:Forms:ScrollBars:Vertical;

this->textBox2->Size = System: Drawing:Size (147, 20);

this->textBox2->TabIndex = 3;

// button1

this->button1->Location = System: Drawing:Point (12, 295);

this->button1->Name = L" button1″ ;

this->button1->Size = System: Drawing:Size (75, 23);

this->button1->TabIndex = 4;

this->button1->Text = L" Поиск" ;

this->button1->UseVisualStyleBackColor = true;

this->button1->Click += gcnew System: EventHandler (this, &Form1:button1_Click);

// textBox3

this->textBox3->AcceptsReturn = true;

this->textBox3->ImeMode = System: Windows:Forms:ImeMode:NoControl;

this->textBox3->Location = System: Drawing:Point (213, 180);

this->textBox3->Multiline = true;

this->textBox3->Name = L" textBox3″ ;

this->textBox3->ReadOnly = true;

this->textBox3->ScrollBars = System: Windows:Forms:ScrollBars:Vertical;

this->textBox3->Size = System: Drawing:Size (263, 54);

this->textBox3->TabIndex = 5;

// label1

this->label1->AutoSize = true;

this->label1->Location = System: Drawing:Point (269, 108);

this->label1->Name = L" label1″ ;

this->label1->Size = System: Drawing:Size (152, 13);

this->label1->TabIndex = 6;

this->label1->Text = L" Введите искомую подстроку" ;

// label2

this->label2->AutoSize = true;

this->label2->Location = System: Drawing:Point (46, 25);

this->label2->Name = L" label2″ ;

this->label2->Size = System: Drawing:Size (107, 13);

this->label2->TabIndex = 7;

this->label2->Text = L" Содержимое файла" ;

// label3

this->label3->AutoSize = true;

this->label3->Location = System: Drawing:Point (295, 159);

this->label3->Name = L" label3″ ;

this->label3->Size = System: Drawing:Size (106, 13);

this->label3->TabIndex = 8;

this->label3->Text = L" Результаты поиска" ;

// button2

this->button2->Location = System: Drawing:Point (12, 339);

this->button2->Name = L" button2″ ;

this->button2->Size = System: Drawing:Size (111, 23);

this->button2->TabIndex = 9;

this->button2->Text = L" Заполнить массив" ;

this->button2->UseVisualStyleBackColor = true;

this->button2->Click += gcnew System: EventHandler (this, &Form1:button2_Click);

// button3

this->button3->Location = System: Drawing:Point (401, 441);

this->button3->Name = L" button3″ ;

this->button3->Size = System: Drawing:Size (75, 23);

this->button3->TabIndex = 11;

this->button3->Text = L" Выход" ;

this->button3->UseVisualStyleBackColor = true;

this->button3->Click += gcnew System: EventHandler (this, &Form1:button3_Click);

// label6

this->label6->AutoSize = true;

this->label6->Location = System: Drawing:Point (247, 250);

this->label6->Name = L" label6″ ;

this->label6->Size = System: Drawing:Size (125, 13);

this->label6->TabIndex = 14;

this->label6->Text = L" Количество символов: «;

// label4

this->label4->AutoSize = true;

this->label4->Location = System: Drawing:Point (247, 274);

this->label4->Name = L" label4″ ;

this->label4->Size = System: Drawing:Size (43, 13);

this->label4->TabIndex = 12;

this->label4->Text = L" Время:" ;

// button4

this->button4->Location = System: Drawing:Point (12, 383);

this->button4->Name = L" button4″ ;

this->button4->Size = System: Drawing:Size (111, 23);

this->button4->TabIndex = 16;

this->button4->Text = L" Добавить строку" ;

this->button4->UseVisualStyleBackColor = true;

this->button4->Click += gcnew System: EventHandler (this, &Form1:button4_Click);

// textBox4

this->textBox4->Location = System: Drawing:Point (139, 386);

this->textBox4->Name = L" textBox4″ ;

this->textBox4->Size = System: Drawing:Size (237, 20);

this->textBox4->TabIndex = 17;

// button5

this->button5->Location = System: Drawing:Point (12, 430);

this->button5->Name = L" button5″ ;

this->button5->Size = System: Drawing:Size (111, 23);

this->button5->TabIndex = 18;

this->button5->Text = L" Удалить строку" ;

this->button5->UseVisualStyleBackColor = true;

this->button5->Click += gcnew System: EventHandler (this, &Form1:button5_Click);

// textBox5

this->textBox5->Location = System: Drawing:Point (139, 433);

this->textBox5->Name = L" textBox5″ ;

this->textBox5->Size = System: Drawing:Size (237, 20);

this->textBox5->TabIndex = 19;

// label7

this->label7->AutoSize = true;

this->label7->Location = System: Drawing:Point (196, 414);

this->label7->Name = L" label7″ ;

this->label7->Size = System: Drawing:Size (122, 13);

this->label7->TabIndex = 20;

this->label7->Text = L" Введите номер строки" ;

// label8

this->label8->AutoSize = true;

this->label8->Location = System: Drawing:Point (210, 367);

this->label8->Name = L" label8″ ;

this->label8->Size = System: Drawing:Size (86, 13);

this->label8->TabIndex = 21;

this->label8->Text = L" Введите строку" ;

// menuStrip1

this->menuStrip1->Items->AddRange (gcnew cli: array< System: Windows:Forms:ToolStripItem^ >(1) {this->файлToolStripMenuItem});

this->menuStrip1->Location = System: Drawing:Point (0, 0);

this->menuStrip1->Name = L" menuStrip1″ ;

this->menuStrip1->Size = System: Drawing:Size (487, 24);

this->menuStrip1->TabIndex = 22;

this->menuStrip1->Text = L" menuStrip1″ ;

// файлToolStripMenuItem

this->файлToolStripMenuItem->DropDownItems->AddRange (gcnew cli: array< System: Windows:Forms:ToolStripItem^ >(2) {this->открытьToolStripMenuItem,

this->очиститьМассивСтруктурToolStripMenuItem});

this->файлToolStripMenuItem->Name = L" файлToolStripMenuItem" ;

this->файлToolStripMenuItem->Size = System: Drawing:Size (48, 20);

this->файлToolStripMenuItem->Text = L" Файл" ;

// открытьToolStripMenuItem

this->открытьToolStripMenuItem->Name = L" открытьToolStripMenuItem" ;

this->открытьToolStripMenuItem->Size = System: Drawing:Size (126, 22);

this->открытьToolStripMenuItem->Text = L" Открыть" ;

this->открытьToolStripMenuItem->Click += gcnew System: EventHandler (this, &Form1:открытьToolStripMenuItem_Click);

// очиститьМассивСтруктурToolStripMenuItem

this->очиститьМассивСтруктурToolStripMenuItem->Name = L" очиститьМассивСтруктурToolStripMenuItem" ;

this->очиститьМассивСтруктурToolStripMenuItem->Size = System: Drawing:Size (126, 22);

this->очиститьМассивСтруктурToolStripMenuItem->Text = L" Очистить" ;

this->очиститьМассивСтруктурToolStripMenuItem->Click += gcnew System: EventHandler (this, &Form1:очиститьМассивСтруктурToolStripMenuItem_Click);

// openFileDialog1

this->openFileDialog1->FileName = L" openFileDialog1″ ;

// Form1

this->AllowDrop = true;

this->AutoScaleDimensions = System: Drawing:SizeF (6, 13);

this->AutoScaleMode = System: Windows:Forms:AutoScaleMode:Font;

this->ClientSize = System: Drawing:Size (487, 465);

this->Controls->Add (this->label8);

this->Controls->Add (this->label7);

this->Controls->Add (this->textBox5);

this->Controls->Add (this->button5);

this->Controls->Add (this->textBox4);

this->Controls->Add (this->button4);

this->Controls->Add (this->label6);

this->Controls->Add (this->label4);

this->Controls->Add (this->button3);

this->Controls->Add (this->button2);

this->Controls->Add (this->label3);

this->Controls->Add (this->label2);

this->Controls->Add (this->label1);

this->Controls->Add (this->textBox3);

this->Controls->Add (this->button1);

this->Controls->Add (this->textBox2);

this->Controls->Add (this->textBox1);

this->Controls->Add (this->radioButton2);

this->Controls->Add (this->radioButton1);

this->Controls->Add (this->menuStrip1);

this->MainMenuStrip = this->menuStrip1;

this->Name = L" Form1″ ;

this->RightToLeftLayout = true;

this->Text = L" Form1″ ;

this->Load += gcnew System: EventHandler (this, &Form1:Form1_Load);

this->menuStrip1->ResumeLayout (false);

this->menuStrip1->PerformLayout ();

this->ResumeLayout (false);

this->PerformLayout ();

}

#pragma endregion

int LineFind (array^ fstr, int m)

{

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

while (true)

{

k++;kol++;

s = strlen (arr[k]. str);

if (arr[k].id ≠ -10)

{

i=-1;kol++;

while (true)

{

i++;

j=0;kol++;

while ((j

{

kol++;

j++;

if ((j==m)||(i==s-m))

{

kol++;

if (j==m)

{

kol++;

textBox3->Text +="Подстрока найдена в строке «+ (k) + «по адресу «+ (i) + «rn» ;

res=1;

}

}

}

if (i>s) break;

}

if (k==n)

break;

}

}

return res;

}

int Addline ()

{

String^ str = textBox4->Text;

longstr = longstr + str->Length;

if (str->Length≠0)

{

n++;

arr[n]. id=n;

char* str2 = (char*)(void*)Marshal:StringToHGlobalAnsi (str);

strcpy (arr[n]. str, str2);

textBox1->Text += arr[n]. id + ": «+ gcnew String (arr[n]. str) + «rn» ;

//kolstr = kolstr + n;

//label5->Text = «Количество элементарных итераций: «+ (n);

return 1;

}

else

return 0;

}

void ShowStruct ()

{

for (int i=0;i<=n;i++)

if (arr[i]. id ≠ -10)

textBox1->Text += arr[i]. id + ": «+ gcnew String (arr[i]. str) + «rn» ;

}

int algorithm_KMP (array^ fstr, int l)

{

int i=0, j=-1, N, M;

N = strlen (arr[l]. str);

M = fstr->Length;

int *d =(int*)malloc (M*sizeof (int)); // динамический массив длины М

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

d[0]=-1;

while (i

{

kol++;

while ((j>=0) && (fstr[j]≠fstr[i]))

{

j = d[j];

kol++;

}

i++;

j++;

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

{

d[i]=d[j];

kol++;

}

else

{

d[i]= j;

kol++;

}

}

/* поиск */

for (i=0,j=0;(i

while ((j>=0)&&(fstr[j]≠arr[l]. str[i]))

{

j=d[j];

kol++;

}

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

if (j==M)

return i-j;

else /* i==N */

return -1;

}

private: System: Void textBox1_TextChanged (System:Object^ sender, System: EventArgs^ e)

{

}

private: System: Void Form1_Load (System:Object^ sender, System: EventArgs^ e)

*.txt

private: System: Void button2_Click (System:Object^ sender, System: EventArgs^ e)

{

textBox1->Clear ();

if (wcslen (file)≠0)

{

ifstream input;

input.open (file);

while (!input.eof ())

{

n++;

input>>arr[n]. str;

longstr=longstr + strlen (arr[n]. str);

arr[n].id = n;

}

input.close ();

ShowStruct ();

label6->Text = «Количество символов: «+ longstr;

}

else

MessageBox:Show («Выберите файл: Файл — открыть»);

}

private: System: Void button1_Click (System:Object^ sender, System: EventArgs^ e)

{

if (n ≠ -1)

{textBox3->Clear ();

int a, b=0;

kol = 0;

double Time1, Time2;

array^ fstr = textBox2->Text->ToCharArray ();

m = fstr->Length;

if (m ≠ 0)

{

Time1 = omp_get_wtime ();

if (choice==1)

{

if (LineFind (fstr, m)==0)

textBox3->Text = «Подстрока не найдена» ;

kol=0;

}

if (choice==2)

{

for (int l=0;l<=n;l++)

{

kol++;

a=algorithm_KMP (fstr, l);

if (a ≠ -1)

{

textBox3->Text +="Подстрока найдена в строке «+ (l) + «по адресу «+ (a) + «rn» ;

b=1;

}

}

if (b == 0)

textBox3->Text = «Подстрока не найдена» ;

kol=0;

}

Time2 = omp_get_wtime ();

Time2 = Time2 — Time1;

label4->Text ="Время: «+ String: Format («{0:F5}», Time2);

}

else

MessageBox:Show («Введите искомую подстроку»);

}

else

MessageBox:Show («Массив структур не заполнен»);

}

private: System: Void radioButton1_CheckedChanged (System:Object^ sender, System: EventArgs^ e)

{

choice = 1;

}

private: System: Void radioButton2_CheckedChanged (System:Object^ sender, System: EventArgs^ e)

{

choice = 2;

}

private: System: Void button3_Click (System:Object^ sender, System: EventArgs^ e)

{

delete[] arr;

this->Close ();

}

private: System: Void button4_Click (System:Object^ sender, System: EventArgs^ e)

{

if (Addline ()==1)

{

label6->Text = «Количество символов: «+ longstr;

MessageBox:Show («Элемент добавлен»);

}

else

MessageBox:Show («Ошибка при добавлении элемента»);

}

private: System: Void button5_Click (System:Object^ sender, System: EventArgs^ e)

{

if (n≠-1)

{

int number=-1;

if (textBox5->Text ≠ «»)

{

number = Convert: ToInt32(textBox5->Text);

if (number≠-1)

{

for (int i=0;i<=n;i++)

if (arr[i]. id == number)

{

longstr = longstr — strlen (arr[i]. str);

arr[i].id=-10;

}

label6->Text = «Количество символов: «+ longstr;

textBox1->Clear ();

ShowStruct ();

}

MessageBox:Show («Удаление успешно»);

}

else

MessageBox:Show («Произошла ошибка при удалении»);

}

else

MessageBox:Show («Заполните массив структур»);

}

private: System: Void очиститьМассивСтруктурToolStripMenuItem_Click (System:Object^ sender, System: EventArgs^ e)

{

textBox1->Clear ();

textBox2->Clear ();

textBox3->Clear ();

textBox4->Clear ();

textBox5->Clear ();

longstr = 0;

label6->Text = «Количество символов: «;

label4->Text ="Время: «;

delete[] arr;

arr=new line[10 000];

n=-1;

}

private: System: Void открытьToolStripMenuItem_Click (System:Object^ sender, System: EventArgs^ e)

{

openFileDialog1->ShowDialog ();

if (openFileDialog1->FileName == nullptr) return;

try

{

String^ filename = openFileDialog1->FileName;

pin_ptr whs =PtrToStringChars (filename);

wcscpy_s (file, whs);

auto MyReader = gcnew IO: StreamReader (openFileDialog1->FileName, System: Text:Encoding:GetEncoding (1251));

textBox1->Text= MyReader->ReadToEnd ();

MyReader->Close ();

}

catch (IO:FileNotFoundException^ Ситуация)

{

MessageBox:Show (Ситуация->Message + «nФайл не найден», «Ошибка», MessageBoxButtons: OK, MessageBoxIcon: Exclamation);

}

catch (Exception^ Ситуация)

{

MessageBox:Show (Ситуация->Message, «Ошибка», MessageBoxButtons: OK, MessageBoxIcon: Exclamation);

}

}

};

}