POJ 1961 C++ （KMP）

#include<iostream>
using namespace std;
int n,next[1000008];
char s[1000008];
void Get_next()
{int j,k;
j=1;
k=0;
next[1]=0;
while(j<=n+1)
       { if(k==0 || s[j]==s[k])
            { j++;
              k++;
              next[j]=k;
             }
          else
             k=next[k];
         }
}
int main()
{ int i,cnt,k;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
   k=1;
  while(scanf("%d\n",&n),n!=0)
         { for(i=1;i<=n;i++)
                s[i]=getchar();
           s[i]='#';
           Get_next();
           printf("Test case #%d\n",k++);
           for(i=2;i<=n;i++)
                if(i%(i+1-next[i+1])==0)
                    { cnt=i/(i+1-next[i+1]);
                      if(cnt!=1)
                      printf("%d %d\n",i,cnt);
                     }

        printf("\n");    
     }
   return 0;
}             

该题的题意是这样的，给若干个字符串，判断该字符串的前n位最多重复了几次，比如，给ababab，结果是前4位重复了2次，前6位重复了3次，忽略重复一次的情况.现在我们将注意力放在一个给定的字符串重复了多少次，然后做一个循环就可以求出所有的结果。
我们要根据kmp算法中的next函数来解决这个问题，以ababab为例加以说明：
String：ababab
Next： 0112345
这里根据后面的需要多计算了一位next值。
我们用ababab即作为主串有作为模式串来进行匹配，假设匹配到第7为时不匹配了(下标中1开始)，要根据next[7](=5)的值继续匹配：
ababab*
ababab&
ababab*
ababab
这样，我们用（length+1）-next[length+1]就是字符串向右移动的位数，在该例中为7-5=2.然后用总的长度除以这个向右移动的位数，如果能除尽的话，结果就是重复的次数，否则重复的次数为1                  

posted on 2008-11-26 01:13 蜗牛 阅读(816) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC