Period

这道题可以想到用KMP来解决,根据定义,对于每一个i,S[1-Nxt[i]+1~i]=S[1~Nxt[i]],并且不存在更大的循环节

主要性质:

  • 必要性:若循环元为len,当且仅S[1~i-len]=S[len+1~i]
  • 充分性:从S[1~i-len]与S[len+1~i]各取len个字符,则S[1~len]=S[len+1~2*len],并以此类推,可以得出循环节的结论

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N],n,cnt;
char a[N];
inline void pre(){
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&a[i]!=a[j+1])j=nxt[j];
        if(a[i]==a[j+1])++j;
        nxt[i]=j; 
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%s",&n, a+1);
        pre();
        printf("Test case #%d\n",++cnt);
        for(int i=1;i<=n;i++)
         if(i%(i-nxt[i])==0&&i/(i-nxt[i])>1)//注意特判要大于1的循环次数
          printf("%d %d\n",i,i/(i-nxt[i]));
        puts("");
    }
}

 

上一篇:php – 查找一个月的每周时段(从星期一开始)


下一篇:contentType