有一个字符串T。字符串S的F函数值可以如下计算：F(S) = L * S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。
输入
输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。
输出
输出T的所有子串中长度与出现次数的乘积的最大值。
输入样例
aaaaaa
输出样例
12
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int sa[maxn], rak[maxn]; int tx[maxn], height[maxn]; char s[maxn]; int n, m, p; int cnt[maxn]; struct node { int x, y, id; }a[maxn], b[maxn]; void rsort() { for (int i = 1; i <= m; i++) tx[i] = 0; for (int i = 1; i <= n; i++) tx[a[i].y]++; for (int i = 1; i <= m; i++) tx[i] += tx[i - 1]; for (int i = 1; i <= n; i++) b[tx[a[i].y]--] = a[i]; for (int i = 1; i <= m; i++) tx[i] = 0; for (int i = 1; i <= n; i++) tx[b[i].x]++; for (int i = 1; i <= m; i++) tx[i] += tx[i - 1]; for (int i = n; i >= 1; i--) a[tx[b[i].x]--] = b[i]; } void ssort() { rsort(); p = 0; for (int i = 1; i <= n; i++) { if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) ++p; rak[a[i].id] = p; } for (int i = 1; i <= n; i++) { a[i].x = rak[i]; a[i].id = sa[rak[i]] = i; a[i].y = 0; } m = p; } void solve() { m = 127; for (int i = 1; i <= n; i++) { a[i].x = a[i].y = s[i]; a[i].id = i; } ssort(); for (int j = 1; j <= n; j <<= 1) { for (int i = 1; i + j <= n; i++) { a[i].y = a[i + j].x; } ssort(); if (p == n) break; } } void get_Height() { int k = 0; for (int i = 1; i <= n; i++) { if (k) k--; int j = sa[rak[i] - 1]; while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rak[i]] = k; } } int main() { scanf("%s", s + 1); n = strlen(s + 1); solve(); get_Height(); int mm = 1e8; for (int i = rak[1] + 1; i <= n; i++) { mm = min(mm, height[i]); cnt[mm]++; } mm = 1e8; for (int i = rak[1]; i >= 1; i--) { mm = min(mm, height[i]); cnt[mm]++; } for (int i = n; i >= 1; i--) { cnt[i] += cnt[i + 1]; } long long ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, 1LL * i * (cnt[i] + 1)); } printf("%lld\n", ans); return 0; }
