题解：P10420 [蓝桥杯 2023 国 A] 子串

Yukii_P · 2025-04-18 07:59:06 · 题解

题意简述

计算字符串 S 总共出现过 k 次的子串的个数，其中 k \in \left[1,\lvert S \rvert\right] 。

题目分析

询问所有子串的出现次数，容易想到使用后缀自动机来解决。建好后缀自动机后再建立后缀链接树，可以计算每个 endpos 状态对应子字符串的出现次数；记后缀自动机上某个点为 i，其后缀链接为 fa[i]，这个节点对应的最长子字符串长度为 len[i]，由于后缀自动机上对应子串长度是连续递增的，这个节点对应的子字符串集合的大小就是 len[i]-len[fa[i]]，我们统计所有的节点信息即可。

时间复杂度 O(n)，可以通过本题。

参考代码

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

using namespace std;
using i64 = long long;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<array<int, 26>> ch(n * 2);
    vector<int> fa(n * 2), len(n * 2);
    vector<i64> cnt(n * 2);
    int np = 1, tot = 1;
    auto extend = [&](int c) {
        int p = np;
        np = ++tot;
        len[np] = len[p] + 1; cnt[np] = 1;
        for ( ; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
        if (p == 0) fa[np] = 1;
        else {
            int q = ch[p][c];
            if (len[p] + 1 == len[q]) fa[np] = q;
            else {
                int nq = ++tot;
                len[nq] = len[p] + 1;
                fa[nq] = fa[q], fa[q] = fa[np] = nq;
                for ( ; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
                ch[nq] = ch[q];
            }
        }
    };
    for (char c : s) extend(c - 'a');
    vector<i64> ans(n + 1);
    vector<vector<int>> e(n * 2);
    for (int i = 2; i <= tot; ++i) e[fa[i]].push_back(i);
    auto dfs = [&](auto&& dfs, int u) -> void {
        for (int v : e[u]) {
            dfs(dfs, v);
            cnt[u] += cnt[v];
        }
    };
    dfs(dfs, 1);
    for (int i = 2; i <= tot; ++i) {
        ans[cnt[i]] += len[i] - len[fa[i]];
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
}

signed main() {

    FIO;
    solve();

    return 0;
}