Z-функция, Префикс-Функция, Бор, Манакер

Z-функция

Z-функция - это длина максимального префикса подстроки S, который начинается в x, который одновременно является префиксом нашей строки S
s[x ... x + k] == s[0 ... k]

Код:

int n;
str s;
vector<int> z(n);
int l = 0, r = 0;
for(int i = 1; i < n; i++){
    if(i <= r){
        z[i] = min(z[i - l], r - i + 1);
    }
    while(z[i] + i < n && s[z[i]] == s[z[i] + i]){
         z[i]++;
    }
    if(z[i] + i - 1 > r){
        l = i;
        r = z[i] + i - 1;
    }
}

Префикс Функция

Префикс функцией от строки S называется такой массив p, где Pi - это длина наибольшего префикса длинны S, который также является суффиксом i-того префикса (не считая весь i-й префикс)

Например, для строки "aataataa" префикс функция будет равна [0,1,0,1,2,3,4,5]

Код:

int n;
str s;
vector<int> p(n);
for(int i = 1; i < n; i++){
    int tmp = p[i - 1]
    while(s[i] != s[tmp] && tmp){
        tmp = s[tmp - 1]
    }
    if(s[i] == s[tmp]){
        p[i] = tmp + 1;
    }
}

Манакер

Пусть у нас есть строка S и мы хотим в ней найти все подпалиндромы

https://ru.algorithmica.org/cs/string-searching/manacher/ - тут

Бор

Бор — это структура данных для компактного хранения строк