Исследование алгоритма поиска подстроки в строке с помощью Z-алгоритма

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3
1. Z-АЛГОРИТМ ФУНКЦИИ СТРОКИ 5
2. РЕАЛИЗАЦИЯ АЛГОРИТМА ПОИСКА ПОДСТРОКИ В СТРОКЕ С ПОМОЩЬЮ Z-АЛГОРИТМА НА ЯЗЫКЕ С++ 12
ЗАКЛЮЧЕНИЕ 17
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 19

ВВЕДЕНИЕ

Актуальность темы исследования. Одна из категорий правильных способов поиска строки сводится к вычислению в каком-то смысле корреляции двух строк. ...
То есть Z-функция — это вектор длин наибольшего общего префикса строки с ее суффиксом.Отличная фраза, когда надо кого-то запутать или самоутвердиться, а чтобы понять что же это такое, лучше рассмотреть пример.
Исходная строка «ababcaba». Сравнивая каждый суффикс с самой строкой получим табличку для Z-функции:
Префикс суффикса это ничто иное, как подстрока, а Z-функция — длины подстрок, которые встречаются одновременно в начале и в середине.... Во-вторых, если в строке есть некий символ в единственном экземпляре, то совпасть он может только с самим собой, и значит он делит строку на две части, а значение Z-функции нигде не может превысить длины более короткой части.
Использовать эти наблюдения предлагается следующим образом. Допустим в строке«ababcabсacab» мы хотим поискать «abca». Берем эти строчки и конкатенируем, вставляя между ними сентинел: «abca$ababcabсacab».
Целью курсовой работы является исследование алгоритма поиска подстроки в строке с помощью Z-алгоритма