POJ 1961 Period

题目链接http://poj.org/problem?id=1961

该题的题意是这样的，给若干个字符串，判断该字符串的前n位最多重复了几次，比如，给ababab，结果是前4位重复了2次，前6位重复了3次，忽略重复一次的情况.现在我们将注意力放在一个给定的字符串重复了多少次，然后做一个循环就可以求出所有的结果。

　　我们要根据kmp算法中的next函数来解决这个问题，以ababab为例加以说明：

　　String：ababab

　　Next： -1001234

　　这里根据后面的需要多计算了一位next值。

　　我们用ababab即作为主串有作为模式串来进行匹配，假设匹配到第7为时不匹配了(下标中1开始)，要根据next[7](=5)的值继续匹配：

　　ababab*

　　ababab&

　　ababab*

　　ababab

　　这样，我们用（length）-next[length]就是字符串向右移动的位数，在该例中为6-4=2.然后用总的长度除以这个向右移动的位数，如果能除尽的话，结果就是重复的次数，否则重复的次数为1　

本题是POJ 2406的加强版，利用的依旧是KMP算法。我们可以先考虑只有一组模式串的情况，然后用一个循环依次尝试不同长度的模式串即可。

1961

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 1000005
 4 int next[N];
 5 char s[N];
 6 int main()
 7 {
 8     int n,k,len,t=0;
 9     while(scanf("%d",&n)!=EOF&&n!=0)
10     {
11         scanf("%s",s);
12         t++;
13         int i=0,j=-1;
14     next[0]=-1;    
15     while(i<n)
16     {
17         if(j==-1||s[i]==s[j])
18         {
19             ++i;++j;
20                 next[i]=j;
21         }
22         else
23             j=next[j];
24     }
25     printf("Test case #%d\n",t);
26     for(i=2;i<=n;i++)
27     {
28         
29         if(i%(i-next[i])==0&&i/(i-next[i])>1)
30         {
31             printf("%d %d\n",i,i/(i-next[i]));
32         }
33     }
34     printf("\n");
35     }
36     return 0;
37 }

2406

题目链接http://poj.org/problem?id=2406

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 1000001
 4 int next[N];
 5 char str[N];
 6 int main()
 7 {
 8     while(scanf("%s",str)!=EOF)
 9     {
10         if(strcmp(str,".")==0)
11         {
12             break;
13         }
14         int i=0,j=-1;
15         next[0]=-1;
16         while(str[i]!='\0')
17         {
18             if(j==-1||str[i]==str[j])
19             {
20                 ++i;++j;
21                 if(str[i]!=str[j])
22                 {
23                     next[i]=j;
24                 }
25                 else
26                 {
27                     next[i]=next[j];
28                 }
29             }
30             else
31             {
32                 j=next[j];
33             }
34         }
35         j=i-next[i];
36         if(i%j==0)
37             printf("%d\n",i/j);
38         else
39             printf("1\n");
40     }
41     return 0;
42 }