題目在這兒

Period

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6233????Accepted Submission(s): 3015

Problem Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A^K?, that is A concatenated K times, for some string A. Of course, we also want to know the period K.

?

Input The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.

?

Output For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

?

Sample Input 3 aaa 12 aabaabaabaab 0

?

Sample Output Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4 題意：給出一個字符串，然你找到所有的前綴是循環串的前綴長度，和對應的循環節的循環次數 題解：

總結一下，如果對于next數組中的 i，?符合?i % ( i - next[i] ) == 0 && next[i] != 0 ,?則說明字符串0-n-1循環，而且

循環節長度為: ? i - next[i]

循環次數為: ? ? ? i / ( i - next[i] )

如果要問為什么可以自習用幾個栗子，然后啃一啃

或者看這里：

next[i]數組的含義是0-i-1個字符中前next[i]和倒數next[i]是完全相同的，那么如果next[i] < (i-1)/2 （即如果這完全相同的前綴和后綴不重合的話）那么有i-next[i]>(i-1)/2則i不可能有i%[i-next[i]]==0這種情況是不可能有循環串的，因為如果是循環串，公共的前綴和后綴肯定是重合的 下面考慮如果重合的情況，如果重合的話，那么一定有i-next[i]就是最小的循環節長度，自己畫個圖仔細理解一下 然后就有了上面的結論。還是要理解好next的本質才可以 下面給出這個題的代碼： 1 /* 2 對next的理解更深入了點兒。 3 字符編號從0開始，那么if(i%(i-next[i])==0)，注意，還要保證循環次數大于1，則i前面的 4 串為一個輪回串，其中輪回子串出現i/(i-next[i])次。 5 還要注意Next數組處理的是當前這個數的前綴，所以要處理最后一個字符就要再有面再加一位防止漏解 6 Print a blank line after each test case.注意這個pe了一次 7 */ 8 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> 12 using namespace std; 13 const int N = 1000005; 14 char b[N]; 15 int Next[N]; 16 void get_next(int n) 17 { 18 for(int i = 0; i <= n; i++) Next[i]=0; 19 int tm; 20 tm = Next[0] = -1; 21 int j = 0; 22 while(j<n){ 23 if(tm<0||b[j]==b[tm]) { 24 Next[++j] = ++tm; 25 } 26 else tm = Next[tm]; 27 } 28 return; 29 } 30 int main() 31 { 32 int c = 1; 33 int n; 34 while(~scanf("%d",&n),n) 35 { 36 getchar(); 37 scanf("%s",b); 38 b[n] = '#'; 39 get_next(n); 40 printf("Test case #%d\n",c++); 41 for(int i = 1; i <= n; i++){ 42 int t = i - Next[i]; 43 if(i%t==0&&i/t>1){ 44 printf("%d %d\n",i,i/(i-Next[i])); 45 } 46 } 47 printf("\n"); 48 } 49 return 0; 50 }

?

轉載于:https://www.cnblogs.com/shanyr/p/5676573.html

總結

以上是生活随笔為你收集整理的hdu_1358Period(kmp找循环前缀)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。