вається порожнім.
Пусте слово зазвичай позначають буквою L. Length (L) = 0. p> Визначення 4 . Слово X називається префіксом слова Y, якщо є таке слово Z, що Y = XZ. Причому саме слово є префіксом для самого себе (тому знайдеться нульове слово L, що X = LX.
Приклад : слово ab є префіксом слова abcfa.
Визначення 5 . Слово X називається суфіксом слова Y, якщо є таке слово Z, що Y = ZX. Аналогічно, слово є суфіксом самого себе.
Приклад : слово bfg є суфіксом слова vsenfbfg.
Визначення 6 . Слово X називається підрядком рядка Y, якщо знайдуться такі рядки Z 1 і Z 2 , що Y = Z 1 XZ 2 . При цьому Z 1 називають лівим, а Z 2 - правим крилом підрядка. Підрядком може бути й саме слово. Іноді при цьому слово X називають входженням в слово Y. Серед усіх входжень слова X в слово Y, входження з найменшою довжиною свого лівого крила називають першим або головним входженням. Для позначення входження використовують позначення X Y.
Приклад : слова hrf і fhr є підрядками слова abhrfhr, gf sfdgfro.
1.1.2. Поняття про складність алгоритму.
Метою нашої роботи є знайти ефективний алгоритм, однак нічого поки не було сказано про метод оцінки алгоритмів.
Традиційно в програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різної тактовою частотою. [11, с. 38-40]
У даній роботі будуть розглянуті дві характеристики складності алгоритмів - тимчасова і емкостная. Ми не будемо обговорювати логічну складність розробки алгоритму - скільки В«людино-днівВ» потрібно витратити на створення програми, оскільки не представляється можливим дати об'єктивні кількісні характеристики.
Тимчасову складність будемо підраховувати у виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (залежно від алгоритму). Ємкісна складність буде визначатися кількістю змінних, елементів масивів, елементів записів або просто кількістю байт [6, 7, 10, 11].
Ефективність алгоритму також буде оцінюватися за допомогою підрахунку часу виконання алгоритмом конкретно поставленої задачі, тобто за допомогою експерименту, докладніше про це в частині 2 даної праці.
1.2. Алгоритми засновані на методі послідовного пошуку.
1.2.1. Алгоритм послідовного (прямого) пошуку (The Brute Force Algorithm).
Найбільш очевидний алгоритм. Позначимо S - слово, в якому шукається зразок X. Нехай m і n - довжини слів S і X відповідно. Можна порівняти зі словом X всі подслова S, які починаються з позицій 1,2, ..., m-n +1 в слові S; в разі рівності виводиться відповідна позиція (Лістинг 1). [1, 2]
Лістинг 1
Function Search (S: String; X: String; var Place: Byte): Boolean;
{Функція повертає результат пошуку в слові S}
{подслова X. Place - місце першого входження}
var Res: Boolean; i: Integer;
Begin
Res: = FALSE;
i: = 1;
While (i <= Length (S)-Length (X) +1) And Not (Res) do
If Copy (S, i, Length (X)) = X then
begin
Res: = TRUE;
Place: = i
end
else i: = i +1;
Search: = Res
End;
p> Дуже просто, але дуже нерозумно. Адже максимальне, кількість порівнянь дорівнюватиме O ((m-n +1) * n +1), хоча більшість з них насправді зайві. Наприклад, знайшовши рядок aabc і виявивши невідповідність у четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи з наступного символу, хоча це однозначно не приведе до результату.
Наступний метод працює набагато швидше найпростішого, але, на жаль, накладає деякі обмеження на текст і шуканий рядок.
1.2.2. Алгоритм Рабіна.
Алгоритм Рабіна являє собою модифікацію лінійного алгоритму; він заснований на вельми простий ідеї, яку викладемо, слідуючи книзі [13 ,172-173].
В«Уявімо собі, що в слові A, довжина якого дорівнює m, ми шукаємо зразок X довжини n. Виріжемо "Віконечко" розміром n і будемо рухати його по вхідному слову. Нас цікавить, не збігається чи слово в "віконечку" із заданим зразком. Порівнювати по буквах...
