Написание алгоритма поиска

В ходе решения данной задачи выяснилось, что стандартный алгоритм по перебору отдельных символов на совпадение с поисковым запросом неэффективен, так как при совпадении только одной буквы уже срабатывает положительный исход, независимо на последующие символы из запроса. Наиболее эффективен и относительно прост в написании алгоритм Кнута-Морриса-Пратта.

КМП-поиск - эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных.

Классической задачей на префикс-функцию является задача на поиск подстроки в строке (алгоритм КМП был изначально разработан именно для решения этой задачи). Разберём её в качестве примера.

Пусть нам нужно найти подстроку 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. Применение алгоритма Кнута-Морриса-Пратта.