Для чего и как построить Z-массив

Идея состоит в том: чтобы объеденить темплейт и текст и создать единую строку, а после для нее построить Z-array. Если что, на все это нам понадобиться не больше чем линейное время. А вот для построения самого Z-array нам уже понадобиться квадратичная функция.

Для построения нам придется поддерживать определенный интервал L,R, который по факту и содержит необходимую подстроку. Шаги следующие:

1.Если i-шаг> R, то нет префиксной подстроки, которая начинается перед i и заканчивается после i. Поэтому сбрасываются L и R и вычисляются новые

2. Если i <= R, то K = i - L, и тем самым Zi >= min(ZK, R-i + 1)

Появляются 2 случая тогда:

1. Если ZK < R-i + 1 то нет префиксной подстроки и интервал остается прежним

2. Если наоборот больше: то можно расширить интервал

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