fzu 1901 Period II

点击打开链接fzu 1901

思路：kmp+next数组的应用
分析：
1 题目要求的找到所有满足S[i]=S[i+P] for i in [0..SIZE(S)-p-1]的前缀，并且长度为p。利用上面的式子可以等价的得到等式s[0,len-p-1] = s[p , len-1].
2 给个next数组的性质
   假设现在有一个字符串为ababxxxxabab。那么求出的next数组为00012001234，那么前缀和后缀最长的匹配数是4，然后下一个前缀和后缀匹配长度为next[4] = 2 ， 然后下一个为next[2] = 0。
   所以有一个结论就是，假设当前求出的字符串的前缀和后缀的最长的匹配的长度为len，那么下一个满足的前缀和后缀互相匹配的长度为next[len]...依次
3 观察一下上面的等式，我们发现并不是我们所熟悉的前缀和后缀匹配的等价式。那么我们现在来看这个样列
            f z u f z u f z u f   长度为10
next    000 01 2 3 456 7
那么根据next数组就得到前缀和后缀的匹配长度依次为 7 4 1 0 ，那么这时候看看题目的p的可能长度为 3 6 9 10，那么有没有发现规律。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;

#define MAXN 1000010

int Case;
int next[MAXN];
char words[MAXN];

void getNext(){
   int len = strlen(words);
   next[0] = next[1] = 0;

   for(int i = 1 ; i < len ; i++){
      int j = next[i];
      while(j && words[i] != words[j])
          j = next[j];
      next[i+1] = words[i] == words[j] ? j+1 : 0;
   }
}

int main(){
   int t = 1;
   scanf("%d" , &Case);
   while(Case--){
      scanf("%s" , words);
      getNext();
      int len = strlen(words);
      int i = next[len];
      int ans = 1;
      while(i){
         ans++;
         i = next[i];
      }
      printf("Case #%d: %d\n" , t++ , ans);
      i = next[len];
      while(i){
         printf("%d " , len-i);
         i = next[i];
      }
      printf("%d\n" , len);
   }
   return 0;
}