Основные определения поиска подстроки в строке. Простейшие алгоритмы поиска подстроки в строке. Алгоритмы последовательного поиска и Рабина-Карпа, создание и описание программы, реализующей их. Порядок работы с приложением. Тестирование алгоритмов.
Аннотация к работе
Поиск информации - одно из основных использований компьютера, и быстрый поиск точно заданной подстроки в строке является одной из самых простейших задач поиска информации. Данная функция встроена в различные текстовые редакторы и базы данных, что существенно ускоряет процесс поиска информации и редактирование (замену) фрагментов. В настоящее время функции поиска подстроки в строке инкапсулированы во многие высокоуровневые языки программирования. Но стоит помнить, что стандартные функции далеко не самые оптимальные и эффективные, и если основной задачей программы является нахождение подстроки в строке, то необходимо знать принципы организации функций поиска. Строка (слово) - это последовательность знаков, называемых буквами, из некоторого конечного множества, называемого алфавитом. Сложность алгоритма - зависимость объема работы, выполняемой алгоритмом от размера входных данных. Например, при поиске подстроки aabbc, обнаружено несоответствие в пятом символе (совпало только первые четыре), алгоритм продолжит сравнение со следующего символа исходной строки, что явно не приведет к результату. Этот алгоритм выполняет линейный проход по искомому фрагменту ( шагов) и линейный проход по всему тексту ( шагов), стало быть, общее время работы есть . [5] 1.3.1 Алгоритм Кнута-Морриса-Пратта Данный алгоритм был предложен в 1977 году учеными Кнутом, Праттом и независимо от них Моррисом. Предложенный ими метод выполняет предварительную обработку искомой строки. Листинг программного кода алгоритма последовательного поиска представлен в Приложении А, алгоритма Рабина-Карпа в Приложении Б, алгоритма Кнута-Морриса-Пратта в Приложении В и алгоритма Бойера-Мура в приложении Г.