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 蝸牛 閱讀(886) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC