Description

Input

Output

Sample Input

abcdaaaaababab.
Sample Output
143
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.這道題是考察對next數(shù)組性質(zhì)的應(yīng)用。題意相當(dāng)于是求一個長字符串中循環(huán)節(jié)的個數(shù)。
　　由于我們知道next數(shù)組中存的是一個位置(假設(shè)next[j]的值為k，對應(yīng)的字符串為M,如果k>0,那么M[0....k-1]和M[j-k.....j-1]是相同的，并且0...k-1這個序列一定是最長的)，比如a b c a b c d(next值：-1 0 0 0 1 2 3 )，由next[6]=3可知，M[0..2]=M[3..6]，這就找到了循環(huán)節(jié)，于是我們思考從next數(shù)組作為切入點，來找到一種方法來求得循環(huán)節(jié)的個數(shù)。
　　看看next數(shù)組的一個性質(zhì)：next始終是從-1開始增加(在變?yōu)?之前)。這會導(dǎo)致一個有趣的現(xiàn)象：指針回溯的位置，最遠(yuǎn)都是在一個完整的循環(huán)節(jié)之后。其實由定義也能發(fā)現(xiàn)，如果最遠(yuǎn)回溯到了字符串開頭，就會導(dǎo)致j=k,與next數(shù)組的定義中的0<k<j矛盾。這樣，就留出來了一個循環(huán)節(jié)的長度，如果總長度是這個循環(huán)節(jié)長度的整數(shù)倍，那么循環(huán)節(jié)的個數(shù)就是這個倍數(shù)。反之，說明這個字符串并不是在不停地循環(huán)，而是在某些位置加入了一個或幾個不"和諧"的字符，導(dǎo)致指針無法回溯到第一個循環(huán)節(jié)之后，這樣，輸出1就可以了。
#include<stdio.h>#include<string.h>#define MAX_LEN 1000005int  get_next(void);char dest[MAX_LEN];int next[MAX_LEN];int main(){    while(scanf("%s",dest)!=EOF&&dest[0]!='.')    {    int len=get_next();    int flag=len%(len-next[len]);    if(flag==0)    {        printf("%d/n",len/(len-next[len]));    }    else    {        printf("1/n");    }    }    return 0;}int get_next(void){    int len=strlen(dest),i=0,j=-1;    next[0]=-1;    while(i<len)    {    if(j==-1||dest[i]==dest[j])    {        i++;j++;        next[i]=j;    }    else    {        j=next[j];    }    }    return len;}