51nod1277 maximum value in string [KMP]

The prefix of a string is a continuous substring containing the first letter of the character , for example ：abcd All prefixes of are a, ab, abc, abcd. Give a string S, Find all the prefixes , The maximum value of the product of the character length and the number of occurrences .

for example ：S = “abababa” All prefixes are as follows :

“a”, The product of length and number of occurrences 1 * 4 = 4,
“ab”, The product of length and number of occurrences 2 * 3 = 6,
“aba”, The product of length and number of occurrences 3 * 3 = 9,
“abab”, The product of length and number of occurrences 4 * 2 = 8,
“ababa”, The product of length and number of occurrences 5 * 2 = 10,
“ababab”, The product of length and number of occurrences 6 * 1 = 6,
“abababa”, The product of length and number of occurrences 7 * 1 = 7.

among "ababa" There is 2 Time , The product of the two is 10, Is the largest of all prefixes .

Forward thinking ：
By seeking next Array and recursive next The array method records the number of occurrences of the string .
Code ：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#define N 100005
using namespace std;
typedef long long ll;
int f[N],cnt[N];
char str[N];
int len;

void getnext(){
    

    f[0]=0,f[1]=0;
    for(int i=1;i<len;i++){
    
       int j=f[i];
        while(j&&str[i]!=str[j])j=f[j];
        f[i+1]=(str[i]==str[j]?j+1:0);
    }


}
int main(){
    
    cin>>str;
    len=strlen(str);
    getnext();

    for(int i=len;i>=1;i--){
    
        cnt[i]++;
        cnt[f[i]]+=cnt[i];
    }
    ll res=0;

    for(ll i=1;i<=len;i++){
    
        res= max(i*cnt[i],res);
    }

    cout<<res<<endl;

}