题目大意

给出一个字符串，问其是由多少个相同的子串组成的。

思路

一道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<iostream>
#include<stdio.h>
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;q<=m;q++)
	{
		while(k>0&&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。 
	}
}