Period

题面翻译

对于给定字符串 \(S\) 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。

【输入格式】

多组数据，每组数据第一行一个整数 \(n\)，表示字符串 \(s\) 的长度，若 \(n=0\) 则结束输入。

若 \(n\ne0\)，则第二行一个字符串 \(S\)，如题意。

【输出格式】

对于第 \(i\) 组输出，第一行一个字符串 Test case #i。

之后若干行一行两个整数，表示如果字符串 \(S\) 的一个前缀是周期串，它的长度和循环节数量（注意这里的循环节是指长度最小的循环节）。

之后再空一行。

【说明】

\(n\leq10^6\)，字符串 \(S\) 均由小写字母构成。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

3 aaa 12 aabaabaabaab 0

样例输出 #1

case #1 2 2 3 3

Test case #2 2 2 6 2 9 3 12 4 ```

还是熟悉的最小循环节问题，需要注意的是，前缀长度需要大于1，所以需要从2开始判断，最大前缀长度就是$S$的长度。

判断有没有循环节，看$pmt[i-1]$是否存在，计算循环节数量，看$n$%$(n-pmt[n-1])$是否等于0（因为$S$的前缀串$t$需要作为周期串）。

每个测试点之间的空行特判一下即可，看$i==len$是否成立。

## AC代码

```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
int pmt[MAXN],n,cnt;
string s;
void get_pmt(const string& s){
   for(int i=1,j=0;i<s.length();i++){
       while(j&&s[i]!=s[j])j=pmt[j-1];
       if(s[i]==s[j])j++;
       pmt[i]=j;
   }
}
int main(){
   ios::sync_with_stdio(0),cin.tie(0);
   while(1){
       cin>>n;
       if(n==0)break;
       cin>>s;
       int len=s.length();
       memset(pmt,0,sizeof(pmt));
       get_pmt(s);
       cout<<"Test case #"<<++cnt<<"\n";
       for(int i=2;i<=len;i++){
           if(pmt[i-1]&&i%(i-pmt[i-1])==0){
               cout<<i<<" "<<i/(i-pmt[i-1])<<"\n";
           }
           if(i==len){
               cout<<"\n";
           }
       }
   }
   return 0;
}