В ходе решения данной задачи выяснилось, что стандартный алгоритм по перебору отдельных символов на совпадение с поисковым запросом неэффективен, так как при совпадении только одной буквы уже срабатывает положительный исход, независимо на последующие символы из запроса. Наиболее эффективен и относительно прост в написании алгоритм Кнута-Морриса-Пратта.
КМП-поиск - эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных.
Классической задачей на префикс-функцию является задача на поиск подстроки в строке (алгоритм КМП был изначально разработан именно для решения этой задачи). Разберём её в качестве примера.
Пусть нам нужно найти подстроку t в строке s. С помощью префикс-функции это делается тривиально: найдём префикс-функцию от строки t+#+s (решётка обозначает символ, гарантированно не встречающийся ни в одной из строк). Если эта префикс-функция содержит значения равные длине t, значит t входит в s. А именно, пусть π[i]=|t|. Значит s[i −|t|−1] – последний символ вхождения t в s.
рис 5. Пример реализации стандартного алгоритма на совпадение символа на языке C#
рис 7. Пример реализации КМП-поиска(Кнута-Морриса-Пратта) на языке C#
Заключение
По итогам этого проекта я научился важным навыкам:
1. Опыт программирования на языке C#.
2. Опыт работы с Microsoft Visual Studio.
3. Написание полноценных приложений для операционной системы Microsoft Windows.
4. Применение алгоритма Кнута-Морриса-Пратта.