首页 > 代码库 > 2566. [51nod 1129] 字符串最大值
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
【样例输出】
10
【提示】
【来源】
这题也是醉了啊，。。
一开始看到这题的数据范围的时候就感觉有点诡异
然后写了个裸的KMP果不其然只得60分
后来看了一下老师的题解发现根本不用跑KMP，
只要从后往前扫一遍将i和P[i]的值分别计算一下就可以
可是还是有两个点超时
搞了半天才发现原来三目运算符要比if快很多！！！！
坑爹啊。。。、，！！！！=.=
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char a[1000001]; 6 int p [1000001]; 7 int cs[1000001]; 8 int la,lb; 9 int ans=-1;10 void makep()11 {12 p[0]=-1;13 int j=0;14 for(int i=1;i<la;i++)15 {16 j=p[i-1];17 while(a[i]!=a[j+1]&&j>=0)j=p[j];18 p[i]=a[i]==a[j+1]?j+1:-1;19 }20 }21 int main()22 {23 freopen("string_maxval.in","r",stdin);24 freopen("string_maxval.out","w",stdout); 25 gets(a);26 la=strlen(a);27 makep();28 for(int i=la-1;i>=0;i--)29 {30 cs[i]++;31 cs[p[i]]+=cs[i];32 if(cs[i]*(i+1)>ans)33 ans=cs[i]*(i+1);34 }35 printf("%d",ans);36 return 0;37 }
2566. [51nod 1129] 字符串最大值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。