Poj 1961 KMP

题意：给定一个字符串，求他每一个前缀，如果他是周期的，求len/最短循环节。

分析：

复习一下KMP，之前有详细解析。

由于朴素匹配每次移动一位，KMP可以多移动 f[i] 位，f 就是失配函数，失配函数怎么得到，是通过模式串自己匹配自己得到。

地推 f[i+1] ，如果 i+1 失配，那么先看前一个数字，他是否适合，不适合，继续向前。

本题：

应用 f，如果字符串周期，那么他的最短循环节可以通过 f 得到。

f[i] : 根据定义，前缀和后缀的最长公共长度，那么 i - f[i] 就是最短循环节。

需要注意的是，i+1，！！！（自己体会）

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 char P[maxn];

 int f[maxn];

 int main()

 {

     int n,kase = ;

     while(scanf("%d",&n),n) {

         scanf("%s",P);

         f[] = ;f[] = ;

         for(int i=;i<n;i++) {

             int j = f[i];

             while(j&&P[i]!=P[j])

                 j = f[j];

             f[i+] = (P[i] == P[j] ? j+:);

         }

         printf("Test case #%d\n",kase++);

         for(int i=;i<=n;i++) {

             if(f[i]>&&i%(i-f[i])==)

                 printf("%d %d\n",i,i/(i-f[i]));

         }

         puts("");

     }

     return ;

 }

巴特西

Poj 1961 KMP

最新文章

热门文章