51Nod 1277 字符串中的最大值(KMP,裸题)

输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。

输出所有前缀中字符长度与出现次数的乘积的最大值。

abababa

10

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=100010;
 5 char x[maxn];
 6 int kmpnext[maxn];
 7 int len;
 8 int res[maxn];///出现次数
 9 void pre_kmp(char x[],int m,int kmpnext[])
10 {
11     int i,j;
12     j=kmpnext[0]=-1;
13     i=0;
14     while(i<=m)
15     {
16         if(j==-1||x[i]==x[j])
17         {
18             kmpnext[++i]=++j;
19         }
20         else
21         {
22             j=kmpnext[j];
23         }
24     }
25     return;
26 }
27 int main()
28 {
29     cin>>x;
30     len=(int)strlen(x);
31     pre_kmp(x,len,kmpnext);
32     for(int i=len;i>=1;i--)
33     {
34         res[i]++;
35         res[kmpnext[i]]+=res[i];
36     }
37     ll ans=0;
38     for(ll i=1;i<=len;i++)
39     {
40         ans=max(ans,res[i]*i);
41     }
42     cout<<ans<<endl;
43     return 0;
44 }