виконання конкретного завдання в ході експерименту [5].
.2 Найпростіші алгоритми пошуку підрядка в рядку
.2.1 Алгоритм послідовного пошуку
Алгоритм послідовного пошуку - найочевидніший алгоритм. Нехай - рядок, в якій виконується пошук, а - шукане слово, і . Тоді для пошуку підрядка (слова) в рядку можна виконати порівняння кожної підрядка , що починається з позицій , довжиною . І при збігу вивести відповідний номер першого елемента знайденої підрядка [5].
Варто сказати, що це самий неоптимальний і неефективний алгоритм.
У програмі присутні два циклу, причому один з них вкладений. Зовнішній цикл залежить від , а внутрішній в кращому випадку робить операцію і в гіршому операцій. Таким чином, в кращому випадку алгоритм виробляє порівнянь, але в гіршому випадку це порівнянь. Причому, більшість цих порівнянь явно зайві. Наприклад, при пошуку підрядка aabbc, виявлено невідповідність у п'ятому символі (співпало тільки перші чотири), алгоритм продовжить порівняння з наступного символу вихідного рядка, що явно не призведе до результату. На невеликих вхідних даних цей алгоритм пропрацює швидко, але якщо у великому многомегабайтних файлі буде шукатися послідовність обсягом у кілька кілобайт, то чекати доведеться досить довго.
.2.2 Алгоритм Рабіна-Карпа
Алгоритм Рабіна-Карпа являє собою модифіковану версію алгоритму послідовного пошуку. Його відмінною рисою є застосування хешування - перетворення вхідного масиву даних довільної довжини в вихідну бітову рядок фіксованої довжини [5]. p align="justify"> Нехай - рядок, в якій виконується пошук, а - шукане слово. І і . Уявімо В«віконечкоВ» довжини , яке рухається послідовно по рядку , починаючи з першого символу. Будемо обчислювати хеш-функцію для кожного слова довжини . Тоді задача зводиться до порівняння чисел, що, безсумнівно, швидше. І якщо значення хеш-функції слова з В«віконечкаВ» не збігається зі значенням хеш-функції шуканого зразка, то однозначно ці два рядки не збігаються, в іншому випадку виконаємо посимвольного порівняння.
Цей алгоритм виконує лінійний прохід по шуканого фрагменту ( кроків) і лінійний прохід по в...
