POJ_2406

    这个题目一开始AC的时候基本是YY出的，不过后来分析了一下这样确实可以。

    我们先对字符串和它自己做KMP，实际上也就进行普通的KMP问题的预处理阶段，然后去找P[N],P[P[N]],…中是否存在一个值为k的元素使得N%(N-k)==0，其中N为字符串长度。如果找到了k，就输出N/(N-k)即可。当然，N=1时要分开来写。

    至于为什么这样可以，还是举个例子来说明一下吧。不妨假设找到了这样的k，且N是N-k的x倍，于是我们就可以把字符串分成长度相等的x段，那么对应的匹配的情况就可以这样表示出来：

    1   2   3   …   x-1   x

        1   2   …   x-2   x-1   x

    这样，那么根据第2列就可以得到1=2，同时根据第3列就可以得到2=3，就这样一直推下去就可以得到1=2=…=x-1=x，于是我们就找了这样一个长度为N-k的循环节。同时，由于在寻找k的过程中k是单调递减的，那么N-k便是单调递增的，于是我们一定会最先找到长度最小的循环节。

#include
     
       #include
      
        #define MAXD 1000010 char b[MAXD]; int S[MAXD], P[MAXD], N; void solve() {
   int i, j, k; for(i = 1; b[i]; i ++)         S[i] = 0;     N = i - 1;     j = 0;     P[1] = P[0] = 0; for(i = 2; b[i]; i ++)     {
   while(j > 0 && b[j + 1] != b[i])             j = P[j]; if(b[j + 1] == b[i])             ++ j;         P[i] = j;     } if(N == 1)         printf("1\n"); else     {
   for(k = P[N];; k = P[k]) if(N % (N - k) == 0)         {
               printf("%d\n", N / (N - k)); break;         }     } } int main() {
   for(;;)     {
           scanf("%s", b + 1); if(b[1] == '.') break;         solve();     } return 0; }