. блок 2). Пошук завершується після пошуку підрядка P у всіх рядках S, це дозволяє отримати результат про всі знайдених входженнях P в S. Пошук вважається вдалим, якщо кількість збіглися символів дорівнюватиме довжині підрядка (див. Блоки 7-9). Алгоритм містить умову, що запобігає вихід за межі рядка (див. Блок 10). Прохід по кожному символу рядка здійснюється лічильниками (див. Блок 4, блок 6).
Алгоритм Кнута-Морріса-Пратта.
У цьому алгоритмі підрядок (образ) розміром N порівнюється з рядком S розміром M і якщо зустрічається розбіжність, таке порівняння починається з першої несовпадающая позиції в рядку. Якщо збіги взагалі немає, то порівняння починається з наступної позиції в рядку.
Для роботи алгоритму вводиться додатковий масив для обчислення зсуву на черговому кроці - D. Цей масив може бути отриманий на основі аналізу способу Р і залежить тільки від вмісту підрядка. До початку самого пошуку підрядка в рядку можна обчислити значення зрушень, які використовуються в подальшому пошуку. Причому в масив D поміщається значення=- 1, якщо виробляється зрушення на цілий образ. Чим менше значення D, тим на більше число позицій проводиться зсув по рядку. Зрушення для комірки j обчислюється як jd [j]. Основною відмінністю КМП-алгоритму від алгоритму прямого пошуку є здійснення зсуву слова не так на один символ на кожному кроці алгоритму, а на деяке змінне кількість символів. Таким чином, перед тим як здійснювати черговий зсув, необхідно визначити величину зсуву. Для підвищення ефективності алгоритму необхідно, щоб зсув на кожному кроці був би якомога більшою.
Блок схеми алгоритмів представлені див. додаток А.
Розробка структури програми
алгоритм пошук підрядок
На підставі аналізу технічного завдання була розроблена програма пошуку підрядка. В якості основної структури даних використовується масив структур.
Розроблена програма складається з 4 основних функцій: ShowStruct () - функція виведення масиву на екран; LineFind (array lt; Char gt; ^ fstr, int m) - функція прямого пошуку підрядка. Вхід: шукана підрядок, розмір шуканого рядка.
Вихід: Повертає 1 якщо пошук успішний, 0 - якщо не успешен.algorithm_KMP (array lt; Char gt; ^ fstr, int l) - функція пошуку алгоритму Бойєр-Мура. Вхід: шукана підрядок, адреса рядка в масиві рядків. Вихід: повертає адресу строкі.Addline () - функція додавання рядка в масив структур. Вихід: повертає 1 - якщо додавання успішно, 0 - якщо додавання невдало.
Крім основних функцій АТД в програмі присутні функції обробки натискань на кнопки:
private: System :: Void Form1_Load (System :: Object ^ sender, System :: EventArgs ^ e) - функція відкриття форми .: System :: Void button1_Click (System :: Object ^ sender, System :: EventArgs ^ e ) - функція пошуку .: System :: Void button2_Click (System :: Object ^ sender, System :: EventArgs ^ e) - функція завантаження з файлу масиву структур .: System :: Void button3_Click (System :: Object ^ sender, System::EventArgs ^ e) - функція видалення масиву структур і закриття форми.: System :: Void button4_Click (System :: Object ^ sender, System :: EventArgs ^ e) - функція додавання рядка в масив структур.: System :: Void button5_Click ( System :: Object ^ sender, System :: EventArgs ^ e) - функція видалення рядка з масиву структур.: System :: Void очістітьМассівСтруктурToolStripMenuItem_Click (System :: Object ^ sender, System :: EventArgs ^ e) - функція очищення всіх полів і видалення масиву структур.: System :: Void откритьToolStripMenuItem_Click (System :: Object ^ sender, System :: EventArgs ^ e) - функція вибору файлу для читання.
Структурна схема програми представлена ??в додатку А. Вихідний код див. додаток Б.
Опис програми.
У програмі реалізована можливість завантаження тексту з файлу або вручну. Крім цього також реалізована функція видалення рядка. З отриманих даних формується масив структур, розмір якого в подальшому може бути змінений користувачем за допомогою функцій додавання і видалення рядка. Результатом роботи програми є координати знайденого підрядка в тексті і час пошуку, виведені в спеціальні поля. Результати роботи програми виводяться на екран, см.Ріс4-5.
Робота алгоритмів представлена ??скріншотами.
Для заповнення списку рядками можна скористатися можливістю завантаження тексту з файлу: для початку потрібно вибрати файл (Файл - відкрити) см. Рис1.
Рис1. Приклад вибору файлу
Рис2. Додавання рядка
Потім заповнити масив структур за допомогою кнопки «Заповнити масив». Присутня можливість ввести рядки вручну використовуючи кнопку «Додати рядок». Кнопка додавання також надає користувачеві можливість додати рядок до завантаженого з файлу тексту, див. Рис2.
Кнопка «Видалити рядок» реалізує можливість вид...
