1277 字符串中的最大值
题目来源：  Codility
基准时间限制：1 秒 空间限制：131072 KB 分值: 80  难度：5级算法题
一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：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

#include <bits/stdc++.h>
typedef long long ll;


using namespace std;


const int N=1e5+5;
const int INF=0x3f3f3f;


int Next[N];
int cnt[N];
int lenb;
char b[N];


void set_naxt()
{
    int i=0,j=-1;
    Next[0]=-1;
    while(i<=lenb)
    {
        if(j==-1||b[i]==b[j])
        {
            i++; j++;
            Next[i]=j;
        }
        else
        j=Next[j];
    }
}


int main(void){
    cin >>b;
    lenb=strlen(b);
    set_naxt();
    for(int i=1;i<=lenb;i++)    cnt[i]=1;
    for(int i=lenb;i>=1;i--) cnt[Next[i]]+=cnt[i];
    ll ans=-INF;
    for(int i=1;i<=lenb;i++)    ans=max(ans,1LL*i*cnt[i]);
    cout << ans << endl;
}