题目来源： Codility
基准时间限制：1 秒
空间限制：131072 KB 分值: 80
一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。
给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。
例如：S = "abababa" 所有的前缀如下:
"a", 长度与出现次数的乘积 1 * 4 = 4,
"ab",长度与出现次数的乘积 2 * 3 = 6,
"aba", 长度与出现次数的乘积 3 * 3 = 9,
"abab", 长度与出现次数的乘积 4 * 2 = 8,
"ababa", 长度与出现次数的乘积 5 * 2 = 10,
"ababab", 长度与出现次数的乘积 6 * 1 = 6,
"abababa", 长度与出现次数的乘积 7 * 1 = 7.
其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的。
Input
输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。
Output
输出所有前缀中字符长度与出现次数的乘积的最大值。
Input示例
abababa
Output示例
10
分析：kmp裸题，之后会补上纯板子
下面给出AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
char x[maxn];
int kmpnext[maxn];
int len;
int res[maxn];///出现次数
void pre_kmp(char x[],int m,int kmpnext[])
{
int i,j;
j=kmpnext[]=-;
i=;
while(i<=m)
{
if(j==-||x[i]==x[j])
{
kmpnext[++i]=++j;
}
else
{
j=kmpnext[j];
}
}
return;
}
int main()
{
cin>>x;
len=(int)strlen(x);
pre_kmp(x,len,kmpnext);
for(int i=len;i>=;i--)
{
res[i]++;
res[kmpnext[i]]+=res[i];
}
ll ans=;
for(ll i=;i<=len;i++)
{
ans=max(ans,res[i]*i);
}
cout<<ans<<endl;
return ;
}