Z Algorithm

2026-10-24 00:27:40

对于很多算法，网上都有很详细的定义和教学博客，那么我自己在这里，就相当于是简单记一下，方便自己以后翻阅。

$z$ 数组就是每个后缀与原字符串的最长公共前缀的长度，由于 $z_0$ 一般是用不到的，所以一般 $z_0 = 0$ 。

在求 $z$ 数组的时候，我们会有一个区间 $[l, r]$ ，并且 $r = l + z[l] - 1$ ，那么假如 $i \le r$ ，则 $z[i] \ge \min(z[i - l], r - i+ 1)$ . 由于 $z$ 数组的性质， $s[l...r] = s[0...r-l]$ .

若 $i > r$ ，那么只需要遍历求即可，并且更新 $[l, r]$ ，因为 $r$ 递增，所以复杂度为 $\mathcal{O}(n)$ .

CF432D

给一个字符串，找有多少个前缀等于后缀，以及这些前缀出现的次数。

前缀是否等于后缀可以很方便的判断，就是 $z_i = n - i$ . 由于这里只需要统计前缀出现的次数，对于下标 $i$ ，当 $z_i > 0$ 时 $s[i...n-1]$ 里出现了 $s[0...z[i] - 1]$ 。那么长度更小的前缀都出现过了，所以记录一下 $z_i$ 然后求一下后缀和就行。

/*
date: 2026-10-23 23:42:10
path: ~/Projects/cp_code/codeforces/432/D.cpp
*/

#include "bits/stdc++.h"

template <class... Args>
inline void print(std::format_string<Args...> fmt, Args&&... args)
{
    std::cout << std::format(fmt, std::forward<Args>(args)...);
}

template <class... Args>
inline void eprint(std::format_string<Args...> fmt, Args&&... args)
{
    std::cerr << "\033[31m" << std::format(fmt, std::forward<Args>(args)...) << "\033[0m";
}

#ifdef DEBUG
#define dbg(...) eprint("[ {} ] ", __LINE__), eprint(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

void solve()
{
    std::string s;
    std::cin >> s;
    int n = s.size();
    std::vector<int> z(n);
    z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            z[i] = std::max(0, r - i + 1);
            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;
        }
    }
    dbg("{}\n", z);
    std::vector<int> ans, f(n + 1);
    for (int i = 0; i < n; i++) {
        if (z[i] == n - i) {
            ans.push_back(n - i);
        }
        if (z[i]) {
            f[1]++;
            if (z[i] + 1 <= n)
                f[z[i] + 1]--;
        }
    }
    dbg("{}\n", f);
    for (int i = 0, cur = 0; i <= n; i++) {
        cur += f[i];
        f[i] = cur;
    }
    print("{}\n", ans.size());
    for (auto x : ans | std::views::reverse) {
        print("{} {}\n", x, f[x]);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // int testcases;
    // std::cin >> testcases;
    // for (int _ = 0; _ < testcases; _++)
    solve();
}