问题分析

我们需要找到所有恰好出现 $k$ 次的子串，然后按长度分类，找出包含子串数量最多的长度类别（如有多个，取最长的长度）。

关键观察

1. 子串与后缀自动机：一个字符串的所有子串信息可以高效地存储在后缀自动机中
2. endpos 集合：SAM 中每个状态对应一组 endpos 相同的子串，这些子串互为后缀关系
3. 出现次数：状态 $u$ 的出现次数 $cnt[u]$ 就是其 endpos 集合的大小
4. 长度范围：状态 $u$ 包含的子串长度范围是 $[len(link(u)) + 1, len(u)]$

算法思路

步骤1：构建后缀自动机

• 为每个测试用例构建 SAM
• 计算每个状态的出现次数 $cnt[u]$

步骤2：统计恰好出现 k 次的子串

对于每个状态 $u$：

• 如果 $cnt[u] = k$，那么该状态包含的所有子串都恰好出现 $k$ 次
• 这些子串的长度范围是 $[len(link(u)) + 1, len(u)]$
• 我们需要统计每个长度有多少个子串

步骤3：高效区间更新

由于长度范围可能很大，直接枚举会超时。我们使用差分数组技巧：

• 对于区间 $[L, R]$，其中 $L = len(link(u)) + 1$, $R = len(u)$
• 在差分数组 $diff$ 中：
  • $diff[L] += 1$
  • $diff[R + 1] -= 1$

最后通过前缀和还原每个长度的子串数量。

步骤4：寻找答案

• 遍历所有长度，找到子串数量最多的长度
• 如有多个，取最长的
• 如果没有出现 $k$ 次的子串，输出 $-1$

时间复杂度

• 构建 SAM: $O(n)$
• 统计答案: $O(n)$
• 总复杂度: $O(\sum n)$，满足题目要求

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

struct SuffixAutomaton {
    static const int MAXN = 200010;  // 两倍长度
    static const int CHAR = 26;
    
    int len[MAXN], link[MAXN];
    int nxt[MAXN][CHAR];
    int cnt[MAXN];  // 出现次数
    int sz, last;
    
    void init() {
        len[0] = 0;
        link[0] = -1;
        sz = 1;
        last = 0;
        memset(nxt[0], -1, sizeof(nxt[0]));
        memset(cnt, 0, sizeof(cnt));
    }
    
    void extend(int c) {
        int cur = sz++;
        len[cur] = len[last] + 1;
        cnt[cur] = 1;
        memset(nxt[cur], -1, sizeof(nxt[cur]));
        
        int p = last;
        while (p != -1 && nxt[p][c] == -1) {
            nxt[p][c] = cur;
            p = link[p];
        }
        
        if (p == -1) {
            link[cur] = 0;
        } else {
            int q = nxt[p][c];
            if (len[p] + 1 == len[q]) {
                link[cur] = q;
            } else {
                int clone = sz++;
                len[clone] = len[p] + 1;
                memcpy(nxt[clone], nxt[q], sizeof(nxt[q]));
                link[clone] = link[q];
                cnt[clone] = 0;
                
                while (p != -1 && nxt[p][c] == q) {
                    nxt[p][c] = clone;
                    p = link[p];
                }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }
    
    vector<int> build_order() {
        vector<int> order(sz);
        for (int i = 0; i < sz; i++) order[i] = i;
        sort(order.begin(), order.end(), [&](int a, int b) {
            return len[a] > len[b];
        });
        return order;
    }
    
    void compute_cnt() {
        vector<int> order = build_order();
        for (int u : order) {
            if (link[u] != -1) {
                cnt[link[u]] += cnt[u];
            }
        }
    }
};

SuffixAutomaton sam;
const int MAXL = 100010;
ll diff[MAXL];

int solve(const string& s, int k) {
    sam.init();
    for (char c : s) {
        sam.extend(c - 'a');
    }
    sam.compute_cnt();
    
    int n = s.length();
    memset(diff, 0, sizeof(diff));
    
    bool found = false;
    for (int i = 1; i < sam.sz; i++) {
        if (sam.cnt[i] == k) {
            found = true;
            int L = sam.len[sam.link[i]] + 1;
            int R = sam.len[i];
            diff[L]++;
            if (R + 1 <= n) {
                diff[R + 1]--;
            }
        }
    }
    
    if (!found) return -1;
    
    ll max_cnt = 0;
    int ans_len = -1;
    ll current = 0;
    
    for (int len = 1; len <= n; len++) {
        current += diff[len];
        if (current > 0 && (current > max_cnt || (current == max_cnt && len > ans_len))) {
            max_cnt = current;
            ans_len = len;
        }
    }
    
    return ans_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        string s;
        int k;
        cin >> s >> k;
        cout << solve(s, k) << "\n";
    }
    
    return 0;
}

样例验证

用题目给的样例测试：

输入:
6
aab 1
abc 1
aaaa 2
abab 2
ababacc 2
abab 4

输出:
2
1
3
1
2
-1

与题目输出完全一致。

总结

这道题的核心在于：

1. 理解后缀自动机的结构和性质
2. 利用 endpos 集合计算子串出现次数
3. 使用差分数组高效处理区间更新
4. 注意统计的是每个长度的子串数量，而不是出现次数

掌握了后缀自动机，这类子串统计问题就能迎刃而解。