poj 2406 Power Strings（kmp应用)

题意：给出一个字符串s，求重复子串出现的最大次数。

分析：kmp的next[]数组的应用。

要求重复子串出现的最大次数，其实就是求字符串的最小循环节。

以下内容转载于:http://bbezxcy.iteye.com/blog/1377787

------------------------------------------------------------------------------------------------------------------------------

在这里我们假设这个字符串的长度是len，那么如果len可以被len-next[len]整除的话，我们就可以说len-next[len]就是那个最短子串的长度

为什么呢？假设我们有一个字符串ababab,那么next[6]=4对吧，由于next的性质是，匹配失败后，下一个能继续进行匹配的位置，也就是说，把字符串的前四个字母，abab,平移2个单位，这个abab一定与原串的abab重合（否则就不满足失败函数的性质），这说明了什么呢，由于字符串进行了整体平移，而平移后又要重叠，那么必有

s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].说明长度为2的字符串在原串中一定重复出现，这就是len-next[len]的含义！

------------------------------------------------------------------------------------------------------------------------------

国庆做题的效率的确不咋滴呀----=_=效率极其低下，总是做一题，然后就浏览网页，一天下来也做不了2,3 题

一个人做题的确是没什么劲，有点无聊有点闷，还是要有基友搞搞才比较有动力 +_+

打球伤了脚，现在哪都去不了，整天窝在宿舍，好惨的说~~~连解题报告都不想写了......不过还是硬着头皮转载别人的解释写了下来

感觉KMP那些字符串算法好难的说，只是懂了下皮毛，没有深刻理解，题目一变，然后就傻楞了.....无力吐槽了！！！！！

下面是AC代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int N=1000000+5;
 4 char s[N];
 5 int next[N];
 6 void get_next(char s[],int len)
 7 {
 8     int i=0;
 9     int j=-1;
10     next[0]=-1;
11     while(i<=len)
12     {
13         if(j==-1||s[j]==s[i])
14             next[++i]=++j;
15         else
16             j=next[j];
17     }
18 }
19 int main()
20 {
21     while(scanf("%s",s))
22     {
23         if(s[0]=='.')
24             break;
25         int len=strlen(s);
26         get_next(s,len);
27         int k=len-next[len];
28         int ans;
29         if(len%k==0)
30             ans=len/k;
31         else
32             ans=1;
33         printf("%d
",ans);
34     }
35     return 0;
36 }

View Code