Формальна постановка задачі пошуку підрядків

Практична робота №11

Тема: Алгоритми порівняння зі зразком

Мета:

1. Опанувати особливості конкретного середовища програмування.

2. Опанувати методику створення програмного продукту.

3. Реалізувати алгоритм Кнута-Морріса-Пратта.

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

В програмах, призначених для редагування тексту, часто виникає задача пошуку всіх фрагментів тексту, які співпадають із заданим зразком. Звичайно текст – документ, який редагується, а зразок – шукане слово, яке вводиться користувачем. Ефективні алгоритми вирішення цієї задачі можуть підвищувати здатність текстових редакторів до реагування. Крім того, алгоритми пошуку підрядків використовуються, наприклад, для пошуку заданих зразків в молекулах ДНК.

Формальна постановка задачі пошуку підрядків.

Припускається, що текст заданий у вигляді масиву довжини , а зразок – у вигляді масиву довжини . Далі припускається, що елементи масивів і – символи із скінченного алфавіту . Наприклад, алфавіт може мати вид або . Символи масивів і часто називають рядками (strings) або символами.

Кажуть, що зразок зустрічається в тексті зі зсувом , якщо і . Якщо зразок зустрічається в тексті зі зсувом , то величину називають допустимим зсувом; в інакшому випадку її називають недопустимим зсувом. Завдання пошуку підрядків – задача пошуку всіх допустимих зсувів, з якими заданий зразок зустрічається в тексті . В прикладі на рис. 1 видно, що зразок зустрічається в тексті лише один раз, зі зсувом . Кажуть, що зсув є допустимим.

Рис. 1. Задача пошуку підрядків

Існують різні алгоритми пошуку підрядків:

– примітивний;

– скінченний автомат;

– алгоритм Бойєра-Мура;

– алгоритм Рабіна-Карпа;

– алгоритм Ахо-Корасік;

– алгоритм Кнута-Морріса-Пратта;