2566. [51nod 1129] 字符串最大值

【题目描述】

一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：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，是所有前缀中最大的

【输入格式】

输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。 (注意:原题是L <= 10W，这里加强一下!)

【输出格式】

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

【样例输入】

abababa

【样例输出】

【提示】

【来源】

这题也是醉了啊，。。

一开始看到这题的数据范围的时候就感觉有点诡异

然后写了个裸的KMP果不其然只得60分

后来看了一下老师的题解发现根本不用跑KMP，

只要从后往前扫一遍将i和P[i]的值分别计算一下就可以

可是还是有两个点超时

搞了半天才发现原来三目运算符要比if快很多！！！！

坑爹啊。。。、，！！！！=.=

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 char a[];

 int p [];

 int cs[];

 int la,lb;

 int ans=-;

 void makep()

 {

     p[]=-;

     int j=;

     for(int i=;i<la;i++)

     {

         j=p[i-];

         while(a[i]!=a[j+]&&j>=)j=p[j];

         p[i]=a[i]==a[j+]?j+:-;

     }

 }

 int main()

 {

     freopen("string_maxval.in","r",stdin);

     freopen("string_maxval.out","w",stdout);

     gets(a);

     la=strlen(a);

     makep();

     for(int i=la-;i>=;i--)

     {

         cs[i]++;

         cs[p[i]]+=cs[i];

         if(cs[i]*(i+)>ans)

         ans=cs[i]*(i+);

     }

     printf("%d",ans);

     return ;

 }

巴特西