Z - алгоритм

Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна n, а длина шаблона - m, тогда общее затраченное время составит O(m+n) с линейной пространственной сложностью. Для этого мы строим специальный Z-массив.

Что такое Z массив?

Для строки str0..n-1 массив Z имеет ту же длину, что и строка. Элемент Zi массива Z хранит длину самой длинной подстроки, начиная с Zi, которая таке является префиксом str0..n-1

Пример:

str = "aaaaaa"
Z = {x, 5, 4, 3, 2, 1}

Data Science: Алгоритмы и Структуры данных | Чат 💬