Міністерство освіти і науки, молоді та спорту України

Національний університет „Львівська політехніка”

Кафедра САПР

Звіт

про виконання лабораторної роботи № 11

Тема:

Алгоритми пошуку підрядків в рядку

З курсу: Теорія алгоритмів

Виконала:

ст. групи КН-23

Нарушинська О.О.

Прийняв:

Денисюк П.Ю.

Львів - 2011

1.Теоретичні відомості

1.1 Основні визначення

Алгоритими пошуку рядка (англ. string searching algorithms) — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків (зразків, англ. pattern) входять у довший рядок або текст.

Визначення. Рядок (слово) - це послідовність знаків (званих літерами) з деякого кінцевого безлічі, званого алфавітом.

Визначення. Довжина рядка - кількість знаків у рядку.Слова позначаються літерами латинського алфавіту, напр. X = x [1] x [2] ... x [n] - слово довгою n, де x [i] (i-а літера слова) належить алфавітом. Lentgh (X) =  = N - позначення довжини рядка.

Визначення. Слово не містить жодної букви називається порожнім.

Порожнє слово зазвичай позначається буквою L. Length (L) = 0.

Визначення. Слово X називається префіксом слова Y, якщо є таке слово Z, що Y = XZ. Причому саме слово є префіксом для самого себе (тому що знайдеться нульове слово L, що X = LX.

Приклад: слово ab є префіксом слова abcfa.

Визначення. Слово X називається суфіксом слова Y, якщо є таке слово Z, що Y = ZX. Аналогічно, слово є суфіксом самого себе.

Приклад: слово bfg є суфіксом слова vsenfbfg.

Визначення. Слово X називається підрядком рядка Y, якщо знайдуться такі рядки Z ₁ і Z _2, що Y = Z ₁ XZ _2. При цьому Z ₁ називається лівим, а Z ₂ - правим крилом підрядка. Підрядком може бути й саме слово. Іноді при цьому слово X називають входженням в слово Y. Серед всіх входжень слова X в слово Y, входження з найменшою довжиною свого лівого крила називають першим або головним змістом. Для позначення входження використовують позначення X  Y.

Приклад: слова hrf і fhr є підстроками слова abhrfhr, gf  sfdgfro.

У програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, що витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різною тактовою частотою.

Існує дві характеристики складності алгоритмів - тимчасова і емкостная.

Тимчасова складність буде обчислюватися в виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (залежно від алгоритму). Ємнісна складність буде визначатися кількістю змінних, елементів масивів, елементів записів або просто кількістю байт.

Ефективність алгоритму також буде оцінюватися за допомогою підрахунку часу виконання алгоритмом конкретно поставленої задачі, тобто з допомогою експерименту, докладніше про це у розділі 2 даної роботи.

1.2. Алгоритм послідовного (прямого) пошуку

Найбільш очевидний алгоритм. Означене S - слово, у якому шукається зразок X. Нехай m і n - довжини слів S і X відповідно. Можна порівняти зі словом X всі подслова S, які починаються з позицій 1,2 ,..., m-n +1 в слові S; у разі рівності виводиться відповідна позиція.Реалізація цього алгоритму представлена ​​в додатку 1.

Це не ефективний алгоритм тому максимальне, кількість порівнянь дорівнюватиме O ((m-n +1) * n +1), хоча більшість з них насправді зайві. Оцінимо швидкість роботи цього програмного коду. У ній присутні два цикли (один вкладений), час роботи зовнішнього більшим ступенем залежить від n, а внутрішній у гіршому випадку робить m операцій. Таким чином, час роботи всього алгоритму є O ((n-m +1) m).Для маленьких рядків пошук пропрацює швидко, але якщо в якомусь багатомегабайтного файлі буде шукатися послідовність довжиною 100 Кб, то доведеться чекати ну дуже довго. Втім багатьом вистачає і цього. Наприклад, знайшовши рядок aabc і виявивши невідповідність у четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи з наступного символу, хоча це однозначно не призведе до результату.