记录编号	428328	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[51nod 1129] 字符串最大值	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2017-07-25 13:27:35	内存使用	8.90 MiB

#include<bits/stdc++.h>
using namespace std;
int f[1000005],g[1000005];
char a[1000005];
int main()
{
	freopen("string_maxval.in","r",stdin);
	freopen("string_maxval.out","w",stdout);
	scanf("%s",a);
	int lena=strlen(a);
	for(int i=lena;i>=1;i--)
	a[i]=a[i-1];
	for(int i=2;i<=lena;i++)
	{
		int j=f[i-1];
		while(j&&a[j+1]!=a[i])
		j=f[j];
		if(a[j+1]==a[i])
		f[i]=j+1;
		else
		f[i]=0;
	}
	for(int i=1;i<=lena;i++)
	g[i]=1;
	int ma=-1;
	for(int i=lena;i>=1;i--)
	{
		g[f[i]]+=g[i];
		ma=max(ma,i*g[i]);
	}
	cout<<ma;
	return 0;
}
/*
递推式昨天还会今天突然就不会了....屡了半天，大概知道了吧，一个串每出现一次， 
你的最长前缀就多出现一次（递推式初始全是1表示从第一位开始的那个（不是加2不然这个会被重复计算））
至于前缀的前缀，我们乍一看，应该加3次，但只加了2次，是不是就有错呢?事实上是没有的，我们可以
模拟一下这个过程，（ababababcabababababab），（我连自己都说服不了..）往前找的时候
会出现一种情况，（恰好是当时的前缀去掉除其前缀以外的剩余字母（只不过发生在字符串尾部而不是前面））
当时前缀的前缀成了现在的前缀，会给他加上那缺少的一次，如果像我给的样例那样
到达那个位置的时候前缀并不是当时前缀的前缀，也就不会给他加，那该怎么办，我们会发现一直找下去总会有
我所说的那种情况出现，而中间都是重复的（前缀的前缀重复使用（在相邻两个"前缀“中分别充当前缀和后缀）），
所以不需要额外加； 
*/