Z - и префикс - функции Никиту не ждём=(

этой строки — это массив длины N,  i-ый элемент которого равен

наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.

1]
S = “abcabc”
Z(S) = [0, 0, 0, 3, 0, 0]
S

= “aaabaab”
Z(S) = [0, 2, 1, 0, 2, 1, 0]

= “aabaaab”?

посчитать, сколько символов начиная с этого совпадают с первыми символами.

Z[0]

= 0; //Нулевой элемент считается неопределённым
for (i = 1; i < длины строки S; i++) {
d = 0;
while (S[i+d] = S[d] && i+d < длины строки S)
d++;
Z[i] = d;
}

что у нас отрезок S[i]…S[i+Z[i]-1] соответствует отрезку S[0]…S[Z[i]-1]… Значит, просматривая очередной

элемент первого отрезка мы можем взять соответствующее ему значения из второго отрезка. Тогда, очевидно, что для построения эффективного алгоритма нам достаточно хранить крайний правый из рассмотренных отрезков. Это даёт нам возможность построить алгоритм за О(n), ведь внутри этого отрезка мы будем восстанавливать результат однозначно, а расширять этот отрезок мы будем максимум N раз.

0, r = 0
Z[0] = 0
for (i = 1; i

строки S; i++)
{
d = 0
if (i<=r) d = min( r–i+1, Z[i - l])

while (S[i + d] == S[d] && i+d < длины строки S)
d++

if (i+d-1 > r)
l = i, r = i+d-1
Z[i] = d
}

массив чисел pi, где pi[i] определяется следующим образом: это такая наибольшая длина

наибольшего собственного суффикса подстроки S, совпадающего с её префиксом (собственный суффикс — значит не совпадающий со всей строкой). В частности, значение pi[0] полагается равным нулю.

Например, для строки "abcabcd" префикс-функция равна:  [0, 0, 0, 1, 2, 3, 0], что означает:
у строки "a" нет нетривиального префикса, совпадающего с суффиксом;
у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abca" префикс длины 1 совпадает с суффиксом;
у строки "abcab" префикс длины 2 совпадает с суффиксом;
у строки "abcabc" префикс длины 3 совпадает с суффиксом;
у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.
Другой пример — для строки "aabaaab" она равна: [0, 1, 0, 1, 2, 2, 3].

префикс-функции:
vector prefix_function (string s)
{
int n = (int) s.length();

vector pi (n);
for (int i=0; i for (int k=1; k if (s.substr(0,k) == s.substr(i-k+1,k)) pi[i] = k; return pi;
}

значение pi[i+1]  не более чем на единицу превосходит значение pi[i] для любого i.
Т.к. сама

строка не может увеличиться более, чем на единицу, то и её суффикс тоже не может увеличиться больше, чем на единицу… Т.Е. мы можем избавиться от центрального цикла и сравнивать только с суфиксом длины pi[i] + 1. И если суффикс не увеличился на 1, то нужно проверить pi[pi[i+1]]

сравнений подстрок. Для этого постарзаемся максимально использовать информацию, вычисленную на

предыдущих шагах.
Мы точно знаем значение pi[i], это значит, что наш предыдущий префикс закончился в символе с индексом pi[i].
Нужно просто сравнить символы S[pi[i]] и S[i+1]. Если они равны, значит pi[i+1] = pi[i] + 1, иначе проверяем pi[pi[i+1]]. Если мы не нашли совпадений – устанавливаем pi[i+1] = 0
При переходе от pi[i] к pi[pi[i] - 1] – мы двигаемся по префиксу, при этом предыдущие pi[pi[i]] символов префикса остаються равны предыдущим символам суффикса.

0
len = длина строки S
for (i = 1; i

len; i++)
{
j = pi[i-1];
while (j>0 && s[i] != s[j])
j = pi[j-1];

if (s[i] == s[j]) j++

pi[i] = j
}