51nod1277 字符串中的最大值

传送门: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1277

Solution

KMP中next数组可以求出每个前缀最长(小于本身)的border,显然一个前缀A出现的次数就是以A为最大(小于本身)border的前缀个数+1,记cnt[i]为长度为i的前缀出现次数-1,cnt可以逆推求出,所以一遍KMP之后,逆推求cnt,顺便求最大值就好了.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int next[N],cnt[N],j,n;
long long ans;
char s[N];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int i=2;i<=n;i++){
        while (s[i]!=s[j+1]&&j) j=next[j];
        if (s[i]==s[j+1]) j++;
        next[i]=j; cnt[j]++;
    }
    for (int i=n;i;i--){
        ans=max(ans,(long long)i*(cnt[i]+1));
        cnt[next[i]]+=cnt[i];
    }
    printf("%lld",ans);
}