51nod 1277 B - 字符串中的最大值 【KMP+dp】

题目描述：给你一个1e5长度的字符串，问每个字符串在其中出现的次数，求次数乘以长度的最大
分析：这个题一开始就想着要统计每个前缀出现的次数是比较麻烦的，因为字符串的长度太长，时间复杂度远远不够，但是仔细观察，由于都是前缀，所以，我们可以发现，前缀的前缀一定在前缀中重复出现，这句话可能不好理解，举个例子， abababc 他的一个前缀ababab中的前缀为ab 那么我们就可以知道 num[ab]+=num[ababab],根据这个递推关系，我们可以找出dp的状态转移方程，同时利用kmp 的next数组就可以了。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
int next[maxn];
char a[maxn];
void getnext(char a[])
{
    int i=0,j=-1;
    next[0]=-1;
    int len=strlen(a);
    while(i<len)
    {
        if(j==-1||a[i]==a[j])
        {
            next[++i]=++j;
        }
        else j=next[j];
    }
}
int dp[maxn];
int main()
{
    scanf("%s",a);
    int len=strlen(a);
    getnext(a);
    cl(dp);
    for(int i=len;i>=0;i--)
    {
        dp[i]++;
        dp[next[i]]+=dp[i];
    }
    ll ans=0;
    for(int i=1;i<=len;i++)
    {
        ans=max(ans,(ll)dp[i]*i);
    }
    cout<<ans<<endl;
    return 0;
}