给定字符串 s s s,设 w w w 为 s s s 的某一子串,若有 w = x n x 0 w = x^nx_0 w=xnx0 且 x 0 x_0 x0 为 x 的前缀,称 ∣ w ∣ ∣ x ∣ \cfrac{|w|}{|x|} ∣x∣∣w∣ 为 w w w 的 c r i t i c a l e x p o n e n t critical~exponent critical exponent。求 s s s 的所有子串的最大的 c r i t i c a l e x p o n e n t critical~exponent critical exponent。 ( w ≤ 2 e 5 ) (w\leq 2e5) (w≤2e5)
https://vjudge.net/problem/Gym-102411L
首先答案至少为 1 / 1 1/1 1/1,对于 a n s > 1 ans>1 ans>1 的串 t t t,设 t = p r e f i x ( s u f f i x ( i ) ) , j = i + x t = prefix(suffix(i)),~j = i + x t=prefix(suffix(i)), j=i+x,则有 a n s = L C P ( s u f f i x ( i ) , s u f f i x ( j ) ) + j − i j − i = 1 + L C P ( s u f f i x ( i ) , s u f f i x ( j ) ) j − i ans = \cfrac{LCP(suffix(i), suffix(j))+j-i}{j-i}=1+\cfrac{LCP(suffix(i),suffix(j))}{j-i} ans=j−iLCP(suffix(i),suffix(j))+j−i=1+j−iLCP(suffix(i),suffix(j)),故若枚举出所有 L C P LCP LCP 长度对应的后缀集合,则问题得解。为快速求得后缀间的 L C P LCP LCP,可先后缀数组处理。对于确定 L C P LCP LCP 的后缀集合的确定,可将 h e i g h t height height 数组降序扫描,保证了当前枚举到的 h e i g h t [ i ] height[i] height[i] 即是相邻后缀的 L C P LCP LCP,后缀集合用并查集维护,合并时启发式则可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
#define mem(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 2e5 + 5;
const int maxm = 2e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
char s[maxn];
int sa[maxn], rk[maxn], tp[maxn], tax[maxn], hi[maxn];
int pre[maxn];
set<int> st[maxn];
int n, m, P, Q;
void rsort(int n, int m){
for(int i = 0; i <= m; ++i) tax[i] = 0;
for(int i = 1; i <= n; ++i) ++tax[rk[tp[i]]];
for(int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for(int i = n; i >= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}
int cmp(int x, int y, int len, int n){
return tp[x] == tp[y] && x + len <= n && y + len <= n && tp[x + len] == tp[y + len];
}
void da(int n, int m){
for(int i = 1; i <= n; ++i) tp[i] = i, rk[i] = s[i];
rsort(n, m);
for(int len = 1, p = 0; p < n; len <<= 1, m = p){
p = 0;
for(int i = n - len + 1; i <= n; ++i) tp[++p] = i;
for(int i = 1; i <= n; ++i) if(sa[i] > len) tp[++p] = sa[i] - len;
rsort(n, m);
for(int i = 1; i <= n; ++i) tp[i] = rk[i];
rk[sa[1]] = p = 1;
for(int i = 2; i <= n; ++i) rk[sa[i]] = cmp(sa[i - 1], sa[i], len, n) ? p : ++p;
}
int k = 0;
for(int i = 1; i <= n; ++i){
if(k) --k;
int j = sa[rk[i] - 1];
while(s[i + k] == s[j + k]) ++k;
hi[rk[i]] = k;
}
}
int fin(int x){
return x == pre[x] ? x : pre[x] = fin(pre[x]);
}
inline void update(int x, int y){
if(x * 1ll * Q > y * 1ll * P) P = x, Q = y;
}
void unite(int x, int y, int lcp){
int fx = fin(x), fy = fin(y);
if(fx == fy) return;
if(sz(st[fx]) > sz(st[fy])) swap(fx, fy);
for(auto u : st[fx]){
auto pos = st[fy].lower_bound(u);
if(pos != st[fy].end()) update(*pos - u + lcp, *pos -u);
if(pos != st[fy].begin()) --pos, update(u - *pos + lcp, u - *pos);
}
pre[fx] = fy;
for(auto u : st[fx]) st[fy].insert(u);
}
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int cmp2(int x, int y){
return hi[x] > hi[y];
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
da(n, 256);
for(int i = 1; i <= n; ++i) pre[i] = i, st[i].insert(i);
for(int i = 2; i <= n; ++i) tp[i] = i;
sort(tp + 2, tp + 1 + n, cmp2);
P = Q = 1;
for(int i = 2; i <= n; ++i){
int x = sa[tp[i]], y = sa[tp[i] - 1];
unite(x, y, hi[tp[i]]);
}
int d = gcd(P, Q);
printf("%d/%d\n", P / d, Q / d);
return 0;
}