【題目描述】 一個字元串的首碼是指包含該字元第一個字母的連續子串，例如：abcd的所有首碼為a, ab, abc, abcd。 給出一個字元串S，求其所有首碼中，字元長度與出現次數的乘積的最大值。 例如：S = "abababa" 所有的首碼如下: "a", 長度與出現次數的乘積 1 * 4 = 4 ...
【題目描述】
一個字元串的首碼是指包含該字元第一個字母的連續子串，例如：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 }
