ICPC 2019-2020 North-Western Russia Regional Contest L Lengths and Periods

题目描述

https://codeforces.com/gym/102411/problem/L

简要题意：给定一个字符串 $S$，求其价值最大的子串的价值，定义一个字符串 $S$ 的价值为 $\frac{len(S)}{per(S)}$

$n\le 2\times 10^5$

Solution

我们首先将周期转换为 $border$，容易得到串 $S$ 的价值为 $\frac{len(S)}{len(S)-border(S)}$，我们考虑固定 $border(S)=T$，然后我们找最大的 $S$ 满足 $T$ 是 $S$ 的 $border$

考虑后缀自动机，容易发现我们固定 $T$ 后，$S$ 一定是在 $T$ 的子树里，那么我们枚举 $T$ 的任意两个结束位置 $s$ 和 $t$，不妨设 $t<s$，一定可以找到一个 $S$ 满足其结束位置为 $s$，且 $s-t=len(S)-len(T)$，这里我们就成功将 $len(S)-len(T)$ 转换为了结束位置的差，需要注意对于同一对结束位置 $s$ 和 $t$，我们的 $len(T)$ 越大越好，这也就意味着我们只需要在 $s$ 和 $t$ 所代表的节点的 $lca$ 处统计 $s$ 和 $t$ 的贡献即可，那么我们可以直接启发式合并维护 $right$ 集合，在合并的时候顺便统计答案

时间复杂度 $O(n\log ^2 n)$

#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <numeric>
#include <vector>
#define maxn 200010
#define Maxn 400010
using namespace std;

struct SAM {
    int sz, L, l, nxt[26]; 
} T[Maxn]; int f[Maxn], top, last, rt; set<int> S[Maxn]; int id[Maxn];
void init_SAM() {
    for (int i = 1; i <= top; ++i) {
        T[i].sz = T[i].L = T[i].l = f[i] = 0; 
        fill(T[i].nxt, T[i].nxt + 26, 0); 
    }
    rt = last = top = 1; 
    T[rt].L = T[rt].l = f[rt] = 0;
}
void extend(int ch, int k) {
    int np = ++top, p = last; last = np;
    T[np].L = T[p].L + 1; S[np].insert(k);
    while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
    if (!p) return f[np] = rt, void();
    int q = T[p].nxt[ch];
    if (T[q].L - 1 == T[p].L) f[np] = q;
    else {
        int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
        for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[np] = f[q] = nq;
    } 
}

pair<int, int> ans;
inline pair<int, int> max(const pair<int, int>& u, const pair<int, int> &v) {
    if (1ll * u.first * v.second > 1ll * v.first * u.second) return u;
    else return v;
}

vector<int> G[Maxn]; 
void dfs(int u) {
    for (auto v : G[u]) {
        dfs(v);
        if (S[id[u]].size() < S[id[v]].size()) swap(id[u], id[v]);
        for (auto t : S[id[v]]) {
            auto it = S[id[u]].lower_bound(t);
            if (it != S[id[u]].end()) ans = max(ans, make_pair(*it - t + T[u].L, *it - t));
            if (it != S[id[u]].begin()) it = prev(it), ans = max(ans, make_pair(t - *it + T[u].L, t - *it));
        }
        for (auto t : S[id[v]]) S[id[u]].insert(t); 
    }
}

int n;
char s[maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); init_SAM();
    for (int i = 1; i <= n; ++i) extend(s[i] - 'a', i);
    for (int i = 2; i <= top; ++i) G[f[i]].push_back(i);
    for (int i = 1; i <= top; ++i) id[i] = i; ans = make_pair(1, 1), dfs(rt);
    int g = gcd(ans.first, ans.second);
    cout << ans.first / g << "/" << ans.second / g << "\n";
    return 0;
}