Z-функция

Z-функция строки s — массив длин максимальных подстрок, совпадающих с началом всей строки, для каждого индекса i.

vector<int> zFunction(const string &s) {
    vector<int> z(s.size());

    int blockL = 0, blockR = 0;
    for (int i = 1; i < s.size(); i++) {
        int blockLen = 0;

        if (i <= blockR)
            blockLen = min(z[i - blockL], blockR - i + 1);

        while (i + blockLen < s.size() && s[i + blockLen] == s[blockLen])
            blockLen++;

        z[i] = blockLen;

        if (blockR < i + blockLen - 1) {
            blockL = i;
            blockR = i + blockLen - 1;
        }
    }

    return z;
}

Ссылки

• Codeforces EDU — Z-функция
• E-maxx — Z-функция строки
• neerc.ifmo.ru/wiki — Z-функция
• Brestprog — Z-функция
• Algorithmica — Префикс- и Z-функция