Здравствуйте, камрады 😭
Сегодня разбираем строки, а если быть точнее - 🇷🇺-функцию

Определение
Разберем на задаче: пусть дана строка s длины n
Z-функция от этой строки - это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.
Если по простому, z[i] - это наибольший общий префикс строки s и её i-го суффикса.

Пример подсчитанной Z-функции
s = "aaaaa"
z[0] = 0
z[1] = 4
z[2] = 3
z[3] = 2
z[4] = 1

Реализация на С++

vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n);
    
    // L и R - границы отрезка, где мы уже были
    // и знаем, что s[L...R] = s[0...R-L]
    int L = 0, R = 0;
    
    for (int i = 1; i < n; i++) {
        // Если i находится внутри последнего отрезка [L, R]
        if (i <= R) {
            // Используем уже посчитанное значение
            z[i] = min(R - i + 1, z[i - L]);
        }
        
        // Пытаемся увеличить Z-функцию
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        
        // Обновляем границы отрезка, если ушли дальше
        if (i + z[i] - 1 > R) {
            L = i;
            R = i + z[i] - 1;
        }
    }
    
    return z;
}

А где ж применять?
- Поиск подстроки в строке
- Количество различных подстрок в строке
- Сжатие строки
- Поиск палиндромов и других структур

Пример поиска подстроки

vector<int> find_pattern(const string& pattern, const string& text) {
    string concat = pattern + "#" + text;
    vector<int> z = z_function(concat);
    vector<int> matches;
    
    int plen = pattern.length();
    for (int i = plen + 1; i < concat.length(); i++) {
        if (z[i] == plen) {
            matches.push_back(i - plen - 1);
        }
    }
    
    return matches;
}

@postupashki_prog