poj1961Period（next数组）

http://poj.org/problem?id=1961

对于next数组只能说略懂，其中精髓还是未完全领会

大体是本串相同前缀与后缀的最大长度，读不懂？看串abcdab 这里所说前缀与后缀都为ab

这题核心就一句话if((i+1)%(i-next[i])==0) 输出

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 #define INF 0xfffffff
11 #define N 1000010
12 char s[N];
13 int next[N];
14 void kmp(int k)
15 {
16     int i,j=-1;
17     next[0] = -1;
18     for(i = 1 ; i < k ; i++)
19     {
20         while(j>-1&&s[i]!=s[j+1])
21         j = next[j];
22         if(s[i]==s[j+1])
23         j++;
24         next[i] = j;
25     }
26 }
27 int main()
28 {
29     int n,i;
30     int kk=1;
31     while(scanf("%d%*c",&n)!=EOF)
32     {
33         if(!n) break;
34         memset(next,0,sizeof(next));
35         for(i = 0 ; i < n ; i++)
36         scanf("%c",&s[i]);
37         kmp(n);
38         printf("Test case #%d
",kk++);
39         for(i = 0 ;i < n ; i++)
40         if(next[i]!=-1&&(i+1)%(i-next[i])==0)
41         {
42             printf("%d %d
",i+1,(i+1)/(i-next[i]));
43         }
44         puts("");
45     }
46     return 0;
47 }

View Code