му таблицю зміщень зручно вирахувати заздалегідь і зберігати у вигляді одновимірного масиву, де кожному символу з шуканої рядка відповідає зсув щодо останнього символу [6, 8]. p align="justify"> Наведемо приклад роботи алгоритму. Нехай існує алфавіт з п'яти символів: q, w, e, r, t і необхідно знайти входження зразка qwwqr в рядку qwteeqewqrwqwwqr . Наступні схеми ілюструють всі етапи виконання алгоритму. Таблиця зсувів буде виглядати так.
qwert12505
Початок пошуку.
qwteeqewqrwqwwqrqwwqr
Так як останній символ шуканої рядка не співпадає з відповідним символом вихідного рядка, то зразок зміщується вправо на величину з таблиці зміщень, відповідну символу В«eВ» - на 5 позицій.
qwteeqewqrwqwwqrqwwqr
Останні три символи шуканої рядка збіглися при накладенні, а четвертий символ не співпав, значить, відбувається зрушення зразка вправо на одну позицію. br/>
qwteeqewqrwqwwqrqwwqr
Знову не співпадає останній символ шуканої рядка, виконується зсув на 2 позиції вправо.
qwteeqewqrwqwwqrqwwqr
Ще раз виконується зрушення вправо на 2 позиції.
qwteeqewqrwqwwqrqwwqr
У відповідності зі значенням зміщення для символу q виконується зсув на 1 позицію.
qwteeqewqrwqwwqrqwwqr
Алгоритм вважається найшвидшим алгоритмом пошуку, хоча його час роботи в гіршому випадку буде квадратним , але ймовірність цього найгіршого варіанта украй мала. А в середньому же алгоритм показує лінійну залежність від вихідної рядка.
підрядок рядок алгоритм програма
2. Реалізація алгоритмів
У курсовій роботі були реалізовані чотири алгоритму пошуку підрядка в рядку. Лістинг програмного коду алгоритму послідовного пошуку представлений у Додатку А, алгоритму Рабіна-Карпа у Додатку Б, алгоритму Кнута-Морріса-Пратта в Додатку В і алгоритму Бойєр-Мура в додатку Г.
Тестування алгоритмів проводилося на ПК:
Процесор Intel В® Atom в„ў CPU N455 з тактовою частотою 1.66 ГГц
1024 Мб ОЗУ
Компілятор Microsoft Visual Studio 2008.
Всі реалізовані алгоритми були об'єднані в один додаток, який представляє собою інтерфейс користувача для запуску будь-якого з представлених алгоритмів.
.1 Опис програми
Програма розроблена як проект WindowsFormApplication на мові програмування C # в середовищі розробки Microsof...
