首页 > 代码库 > poj 1961 Period
poj 1961 Period
同上
1 #include<cstdio> 2 #include<cstring> 3 #define N 1000005 4 #define LL long long 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 inline int ra() 8 { 9 int x=0,f=1; char ch=getchar(); 10 while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} 11 while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} 12 return x*f; 13 } 14 int n,cas,fail[N]; 15 char ch[N]; 16 int main() 17 { 18 while (scanf("%d",&n)) 19 { 20 if (!n) break; 21 scanf("%s",ch+1); 22 int fix=0; 23 for (int i=2; i<=n; i++) 24 { 25 while (ch[i]!=ch[fix+1] && fix) fix=fail[fix]; 26 if (ch[fix+1]==ch[i]) fix++; fail[i]=fix; 27 } 28 printf("Test case #%d\n",++cas); 29 for (int i=2; i<=n; i++) 30 { 31 int x=i-fail[i]; 32 if (i%x || x==i) continue; 33 printf("%d %d\n",i,i/x); 34 } 35 printf("\n"); 36 } 37 return 0; 38 }
poj 1961 Period
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。