题目大意
给出一个字符串，问其是由多少个相同的子串组成的。
思路
一道KMP题，考验对next[]数组的理解。
next[i]含义是模式串P的前i个字符组成的字符串Pi与其子串（即Pi的子串）匹配的最大长度。例如模式串P=”ababab”，P4就是模式串P的前4个字符组成的字符串”abab”，P4与其子串匹配的最大长度是2（即”abab”与”ab”匹配），则next[4]=2。
由next[i]的理论可以推知，len(p)-next[len(p)]是模式串P的“循环节”长度。为什么循环节长度上要加引号？因为模式串不一定恰好是“循环节”的整数倍，而是其整数倍的子串。在POJ的board里看到了一个非常好的样例，当模式串为”aabaabaa”时，循环节为3。所以在输出答案的时候，要判断模式串P的长度能否整除“循环节”，若不能整除，则输出1。
代码
#include
#include
using namespace std;
#define P_SIZE 1000000
int next[P_SIZE+2];
char P[P_SIZE+2];
//P是模式串。
void COMPUTE_PREFIX_FUNCTION(char P[])
//对next[]进行赋值。
{
int m=strlen(P+1);
next[1]=0;
for(int k=0,q=2;q0&&P[k+1]!=P[q])
k=next[k];
if(P[k+1]==P[q])
k++;
next[q]=k;
}
}
int main()
{
while(scanf("%s",P+1)&&strcmp(".",P+1))
{
COMPUTE_PREFIX_FUNCTION(P);
int len=strlen(P+1),cycle=len-next[len];
//len是模式串P的长度。
//cycle是“循环节”。
printf("%d\n",len%cycle?1:len/cycle);
//若len不能整除cycle时，输出1。
}
}