[cpp]
/*該段話為轉載,很精確.
大致題意：
給出一個字符串，求出這個字符串最多能夠由多少個子串首尾連接而成。比如“ababab”就是由3個“ab”相連而成，所以輸出3，“abcdef”只能看作一個“abcdef”所以輸出1。
大致思路：
KMP中next數組的巧妙運用。在這裡我們假設這個字符串的長度是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]的含義！*/
#include <cstring>
#include <stdio.h>
const int maxn=1000005;
int next[maxn];
void ready(char *mode,int lenb)
{
next[0]=-1;
int j=-1;
for(int i=1; i<lenb; i++)
{
while(j>-1&&mode[j+1]!=mode[i]) j=next[j];
if(mode[j+1]==mode[i]) j++;
next[i]=j;
}
}
int main()
{
char mode[maxn];
while(scanf("%s",mode)!=EOF&&strcmp(mode,".")!=0)
{
int len=strlen(mode);
ready(mode,len);
int m=len-1-next[len-1];
if(len%m==0) printf("%d\n",len/m);
else printf("1\n");
}
return 0;
}
作者：ehi11
