УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Поиск подстрок с помощью конечных автоматов

© И.Р. Ахметов

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Проектная документация
Исполняемая программа и исходные тексты

Аннотация

Задача поиска подстроки в строке является одной из наиболее известных задач информатики. Она тщательна изучена и предложено множество алгоритмов для решения этой задачи и ее модификаций.

В настоящей работе излагается алгоритм поиска подстрок с помощью конечных автоматов. Его достоинства заключаются в его наглядности и простоте и вместе с тем он является линейным от длины текста временем работы (при построенном конечном автомате).

На основе этого алгоритма разработано консольное приложение на языке Pascal.