- 题解
B. 「一本通 2.1 练习 1」Power Strings C题解
- @ 2026-4-11 11:01:44
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int N=1e6+10; const ull B1=131; const ull B2=13131; char s[N]; ull h1[N],h2[N]; ull p1[N],p2[N]; int main(){ p1[0]=p2[0]=1; for(int i=1;i<N;i++){ p1[i]=p1[i-1]*B1; p2[i]=p2[i-1]*B2; } while(scanf("%s",s)1){ if(s[0]'.') break; int n=strlen(s); h1[0]=h2[0]=0; for(int i=0;i<N;i++){ h1[i+1]=h1[i]*B1+(ull)(s[i]); h2[i+1]=h2[i]*B2+(ull)(s[i]); } for(int i=1;i<=n;i++){ if(n%i!=0) continue; bool ok=true; for(int j=i;j<n;j+=i){ ull ref1=h1[i],ref2=h2[i]; ull cur1=h1[j+i]-h1[j]*p1[i]; ull cur2=h2[j+i]-h2[j]*p2[i]; if(cur1!=ref1||cur2!=ref2){ ok=false; break; } } if(ok){ printf("%d\n",n/i); break; } } } return 0; }