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

★★ 输入文件：string_maxval.in 输出文件：string_maxval.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

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

——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
题意：找字符串的各个前缀在字符串中出现的次数，从而的到最大值。

开始认为就是求next[]然后用next[]求各个前缀在字符串中出现的次数，结果只有60分。后来看了其他同学的代码发现了这个比较巧妙的方法。即：任意前缀出现的次数，这个前缀的next(前缀的公共前后缀中的前缀)也会回出现这些次数。
——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<cstring>

 4

 5 using namespace std;

 6 const int maxl=1000010;

 7 char s[maxl],su[maxl];

 8 int next[maxl],l,ans=0,cs[maxl];

 9 void getnext()

10 {

11     next[0]=-1;

12     l=strlen(s);

13     for(int j,i=1;i<l;i++)

14     {

15         j=next[i-1];

16         while(s[i]!=s[j+1]&&j>=0)j=next[j];

17         next[i]=s[i]==s[j+1]?j+1:-1;

18     }

19 }

20 int main()

21 {

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

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

24     scanf("%s",s);

25     getnext();

26     for(int i=l-1;i>=0;--i)

27     {

28         cs[i]++;

29         cs[next[i]]+=cs[i];

30         if(cs[i]*(i+1)>ans)ans=cs[i]*(i+1);

31     }

32     cout<<ans;

33     fclose(stdin);fclose(stdout);

34     return 0;

35 }

巴特西

cogs 2566 字符串最大值