51nod 1292 字符串中的最大值 V2 （后缀数组）-阿里云开发者社区

51nod 1292 字符串中的最大值 V2 （后缀数组）

2023-05-26 125

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 51nod 1292 字符串中的最大值 V2 （后缀数组）

有一个字符串T。字符串S的F函数值可以如下计算：F(S) = L * S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。

输入

输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。

输出

输出T的所有子串中长度与出现次数的乘积的最大值。

输入样例

aaaaaa

输出样例

#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;
}