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;
}             

該題的題意是這樣的，給若干個(gè)字符串，判斷該字符串的前n位最多重復(fù)了幾次，比如，給ababab，結(jié)果是前4位重復(fù)了2次，前6位重復(fù)了3次，忽略重復(fù)一次的情況.現(xiàn)在我們將注意力放在一個(gè)給定的字符串重復(fù)了多少次，然后做一個(gè)循環(huán)就可以求出所有的結(jié)果。
我們要根據(jù)kmp算法中的next函數(shù)來解決這個(gè)問題，以ababab為例加以說明：
String：ababab
Next： 0112345
這里根據(jù)后面的需要多計(jì)算了一位next值。
我們用ababab即作為主串有作為模式串來進(jìn)行匹配，假設(shè)匹配到第7為時(shí)不匹配了(下標(biāo)中1開始)，要根據(jù)next[7](=5)的值繼續(xù)匹配：
ababab*
ababab&
ababab*
ababab
這樣，我們用（length+1）-next[length+1]就是字符串向右移動(dòng)的位數(shù)，在該例中為7-5=2.然后用總的長度除以這個(gè)向右移動(dòng)的位數(shù)，如果能除盡的話，結(jié)果就是重復(fù)的次數(shù)，否則重復(fù)的次數(shù)為1                  

posted on 2008-11-26 01:13 蝸牛 閱讀(887) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC