洛谷P5341 [TJOI2019] 甲苯先生和大中锋的字符串题解

题目链接：P5341 [TJOI2019] 甲苯先生和大中锋的字符串

题意：

大中锋有一个长度为 \(n\) 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。

但是由于字符串很长，大中锋很难将这些子串一一尝试。

这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。

在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 \(k\) 次的子串”。

但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 \(k\) 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。

大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。

输入格式：

第一行一个正整数 \(T\) ，表示有 \(T\) 组测试数据。

接下来 \(T\) 行每行包含一个字符串和一个正整数 \(k\) 。

输出格式：

一共输出 \(T\) 行，每行一个整数表示在出现 \(k\) 次的子串中出现次数的最多的长度。

如果不存在子串出现 \(k\) 次，则输出 \(-1\) 。

数据范围：

\(1\leq n\leq 10^5,~1 \leq T \leq 100,~\sum n \leq 3 \times 10^6\) ，输入的字符串中仅包含小写英文字母。

注意到出现了 \(k\) 次的子串一定为 \(k\) 个后缀的前缀，考虑构建后缀数组。

那么问题就变成了在 height 数组上考察每个长度为 \(k\) 的区间，有多少个公共前缀仅出现在这个区间中。

为什么是仅出现呢？因为一个出现了大于 \(k\) 次的子串也可能出现在这个区间中，挺好理解的吧（

正好上一题有个表格，放过来给大家看看。（当 \(S = \texttt{aabbababb}\) 时后缀的排名） \[ \begin{array}{|l|l|l|l|l|l|l|l|l|} \hline \text { 1 } & \text { 2 } & \text { 3 } & \text { 4 } & \text { 5 } & \text { 6 } & \text { 7 } & \text { 8 } & \text { 9 } \\ \hline \text { b } & & & & & & & & \\ \hline \text { b } & & & \text { b } & & & & & \\ \hline \text { a } & & & \text { b } & & & & & \text { b } \\ \hline \text { b } & & & \text { a } & & \text { b } & & & \text { b } \\ \hline \text { a } & \text { b } & & \text { b } & & \text { b } & & & \text { a } \\ \hline \text { b } & \text { b } & & \text { a } & & \text { a } & \text { b } & & \text { b } \\ \hline \text { b } & \text { a } & \text { b } & \text { b } & & \text { b } & \text { b } & & \text { a } \\ \hline \text { a } & \text { b } & \text { b } & \text { b } & & \text { a } & \text { a } & \text { b } & \text { b } \\ \hline \text { a } & \text { a } & \text { a } & \text { a } & \text { b } & \text { b } & \text { b } & \text { b } & \text { b } \\ \hline \end{array} \] 那么记区间 \([i,i+k-1]\) 的这样的公共前缀的长度为 \(l\) ，显然 \(l\) 属于一个合法区间。

考察 \(l\) 的上界，显然 \(l \le \operatorname{LCP}(i,\,i+k-1)\) ，\(\operatorname{LCP}\) 表示 \(i\) 和 \(i+k-1\) 的最长公共前缀。

接着考察 \(l\) 的下界，由于 \(l\) 不出现在 \([i,\,i+k]\) 或 \([i-1,\,i + k-1]\) ，那么 \[ l > \max\{\operatorname{height}(i), \,\operatorname{height}(i + k)\} \] 也就是说 \[ \max\{\operatorname{height}(i), \,\operatorname{height}(i + k)\} < l \le \min_{i + 1 \le x \le j}\{\operatorname{height}(x)\} \] 前者就是一个取 max ，后者是查询区间 min ，可以用 st 表维护。

然后满足条件的 \(l\) 都可以有，这相当于维护区间加最后全局查，可以差分维护。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define mem(a) memset(a, 0, sizeof(a))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N];
int lg[N], st[18][N]; ll cxy[N];
int n, sa[N], rk[N * 2], tmp[N * 2], height[N], cnt[N];
void sort(const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getheight()
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void getsa()
{
    const int m = max(n, 233);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(m, w); sort(m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
int query(int l, int r)
{
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}
void solve()
{
    int k; cin >> (s + 1) >> k; n = strlen(s + 1);
    for(int i = 1; i <= n + 5; i++) { 
        sa[i] = rk[i] = rk[i + n] = tmp[i] = tmp[i + n] = height[i] = cxy[i] = 0;
    }
    getsa(); getheight();
    for(int i = 1; i <= n; i++) st[0][i] = height[i];
    for(int i = 1; i < 18; i++)
    {
        int *f = st[i], *g = st[i - 1];
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            down(f[j] = g[j], g[j + (1 << (i - 1))]);
    }
    for(int i = 1; i + k - 1 <= n; i++)
    {
        int l = i, r = i + k - 1, L, R;
        if(l == r) R = n - sa[r] + 1; else R = query(l + 1, r);
        L = max(height[l], height[r + 1]) + 1;
        if(L <= R) { ++cxy[L], --cxy[R + 1]; }
    }
    ll ans = -1, mx = 1;
    for(int i = 1; i <= n; i++)
    {
        cxy[i] += cxy[i - 1];
        if(cxy[i] >= mx) { mx = cxy[i], ans = i; }
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i = 2; i <= N - 5; i++) lg[i] = lg[i >> 1] + 1;
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}