next数组
#include <cstdio> #include <cstring> #include <iostream> #include <time.h> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; int const MAXN = 1000010; char s[MAXN]; int next[MAXN]; inline void Get_Next(int n){ memset(next,0,sizeof(next)); for(int i = 1;i < n;i++){ int j = next[i]; while(j && s[i] != s[j]) j = next[j]; if(s[i] == s[j]) next[i + 1] = j + 1; else next[i + 1] = 0; } } int main(){ int T,k = 1; while(~scanf("%d",&T)&&T){ scanf("%s",s); int n = strlen(s); Get_Next(n); printf("Test case #%d\n",k++); for(int i = 1;i <= n;i++){ if(i %(i - next[i]) == 0 && next[i]) printf("%d %d\n",i,i / (i - next[i])); } printf("\n"); } return 0; }