Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).Input
Each test case is a line of input rePResenting s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.Output
For each s you should print the largest n such that s = a^n for some string a.Sample Input
abcdaaaaababab.Sample Output
143Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.這道題是考察對next數組性質的應用。題意相當于是求一個長字符串中循環節的個數。由于我們知道next數組中存的是一個位置(假設next[j]的值為k，對應的字符串為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]，這就找到了循環節，于是我們思考從next數組作為切入點，來找到一種方法來求得循環節的個數。
看看next數組的一個性質：next始終是從-1開始增加(在變為0之前)。這會導致一個有趣的現象：指針回溯的位置，最遠都是在一個完整的循環節之后。其實由定義也能發現，如果最遠回溯到了字符串開頭，就會導致j=k,與next數組的定義中的0<k<j矛盾。這樣，就留出來了一個循環節的長度，如果總長度是這個循環節長度的整數倍，那么循環節的個數就是這個倍數。反之，說明這個字符串并不是在不停地循環，而是在某些位置加入了一個或幾個不"和諧"的字符，導致指針無法回溯到第一個循環節之后，這樣，輸出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;}
新聞熱點
疑難解答
