比赛 字符串练习 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 字符串最大值 最终得分 100
用户昵称 玉带林中挂 运行时间 0.054 s
代码语言 C++ 内存使用 8.90 MiB
提交时间 2017-07-24 22:13:01
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

const int N = 1000000 + 5;

char T[N];
int nxt[N], cnt[N];

int main() 
{
    freopen("string_maxval.in", "r", stdin);
    freopen("string_maxval.out", "w", stdout);
    scanf("%s", T + 1);
    int n = strlen(T + 1);
    for (int i = 2, j = 0; i <= n; i++) 
	{
        while (j && T[j + 1] != T[i]) j = nxt[j];
        if (T[j + 1] == T[i]) j++;
        nxt[i] = j;
    }
    int ans = 0;
    for (int i = n; i; i--) 
	{
        cnt[i]++;
        cnt[nxt[i]] += cnt[i];
        ans = max(ans, i * cnt[i]);
    }
    printf("%d\n", ans);
    fclose(stdin);fclose(stdout);
    return 0;
}