福建省两学一做网站/国内外十大免费crm软件推荐

题目：http://poj.org/problem?id=2406

简单的讲就是找出用多少个最小的子串可以组成给定的字符串。这还是用到了KMP里的前缀-后缀特征，next[len]就是最大的前缀-后缀子串长度。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e6+5;
char str[maxn];
int snext[maxn],len;
void getnext(){int i=0,j=-1;snext[0]=-1;while(i<=len){if(j==-1||str[i]==str[j]){i++;j++;snext[i]=j;}else j=snext[j];}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>str){if(strcmp(str,".")==0)break;len=strlen(str);getnext();int ans=len-snext[len];if(len%ans==0)printf("%d\n",len/ans);else printf("1\n");}return 0;
}