[POJ 2406]Power Strings
转载请注明出处：http://danihao123.is-programmer.com/
循环节又一题……用KMP性质搞搞即可。
注意特判（好像是句废话），再就没啥了……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <cstdio>#include <cstring>const int maxn=1e6+5;char P[maxn];int f[maxn];int main(){ register int i,j,xhj,n; while(scanf("%s",P)){ if(P[0]=='.') break; n=strlen(P); f[0]=f[1]=0; for(i=1;i<n;i++){ j=f[i]; while(j && P[j]!=P[i]) j=f[j]; f[i+1]=(P[j]==P[i]?j+1:0); } xhj=n-f[n]; if(!(n%xhj)){ printf("%d\n",n/xhj); }else{ puts("1"); } } return 0;} |
评论 (0)
