【POJ1961】period

[POJ1961]period

题目描述

如果一个字符串S是由一个字符串T重复K次构成的，则称T是S的循环元。使K出现最大的字符串T称为S的最小循环元，此时的K称为最大循环次数。

现在给定一个长度为N的字符串S，对S的每一个前缀S[1~i],如果它的最大循环次数大于1，则输出该循环的最小循环元长度和最大循环次数。

输入

多组数据，每个数据包括两行。第一行为字符串大小N，第二行包括字符串。输入最后一行以0结尾。

输出

第一行"Test case #"+测试数据第几组，对于每个周期K>1,长度为i的前缀，输出前缀大小i和由单个空格分隔的周期K；前缀必须按照递增排列，每个测试数据之后输出一个空行。

题解思路

• 与自己的前缀进行匹配，与KMP中的next数组的定义相同。next数组的定义是:字符串中以i结尾的子串与该字符串的前缀能匹配的最长长度。

• 将字符串S与自身进行匹配 ,对于每个前缀,能匹配的条件即是:S[i-next[i]+1~i]与S[1~next[i]]是相等的，并且不存在更大的next满足条件。

• 当i-next[i]能整除i时，S[1~i-next[i]]就是S[1~i]的最小循环元。它的最大循环次数就是i/(i - next[i])。

        //#include<bits/stdc++.h>
      #include<string>
      #include<algorithm>
      #include<iostream>
      #include<cstdio>
      using namespace std;
      const int maxn = 1e6+5;
      char s[maxn];
      int next[maxn],n,T;
      void cal(){
          next[1] = 0;
          for(int i = 2,j = 0;i <= n; ++i){
              while(j>0 && s[i] != s[j+1]) j = next[j];
                  if(s[i] == s[j+1]) j++;
                  next[i] = j;
          }
      }
      int main(){
          while(cin >> n && n){
  //            memset(next,0,sizeof(next));
              scanf("%s",s+1);
              cal();
              printf("Test case #%d
",++T);
              for(int i = 2;i <= n; i++){
                  if(i%(i-next[i])==0 && i/(i-next[i]) > 1)
                      printf("%d %d
",i , i/(i-next[i]));
              }
              puts("");
          }
  //        return 0;
      }