记录编号	327194	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2016-10-21 20:37:46	内存使用	12.69 MiB

//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 1000003
char S[Nmax];
int N;
int nt[Nmax] = {0};
void init() {
    scanf("%s", S);
    nt[0] = -1;
    int i;
    int t;
    for (i = 1; S[i] != '\0'; i++) {
        t = i-1;
        while (t >= 0) {
            t = nt[t];
            if (S[t+1] == S[i]) {
                nt[i] = t+1;
                t = 0;
                break;
            }
        }
        if (t < 0)
            nt[i] = -1;
    }
    N = i;
}
typedef long long LL;
LL ans = 0;
LL W[Nmax] = {0};
LL emt = 0;
void work() {
    int t;
    for (int i = N-1; i >= 0; i--) {
        t = nt[i];
        if (t >= 0) {
            ans = max(ans, W[t] + W[i] + (LL)(i-t)*(i-t));
            W[t] = max(W[t], W[i] + (LL)(i-t)*(i-t));
        }
        else {
            ans = max(ans, emt + W[i] + (LL)(i+1)*(i+1));
            emt = max(emt, W[i] + (LL)(i+1)*(i+1));
        }
    }
    printf("%lld\n", ans);
}
int main() {
    freopen("savemzx.in", "r", stdin);
    freopen("savemzx.out", "w", stdout);
    init();
    work();
    return 0;
}
//UBWH