题解 UVA10298 【Power Strings】

# 蒟蒻只会用哈希~~水~~了 ## dalao轻喷 ```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull h[2000000],pw[2000000]; char st[2000000]; ull hsh(ull h[],int l,int r) { return h[r]-h[l-1]*pw[r-l+1]; }//普通的hash int main() { pw[0]=1; for(int i=1;i<=2000000;i++) pw[i]=pw[i-1]*233;//预处理 while(scanf("%s",st)==1&&st[0]!='.') { int l=strlen(st);ull hs=0; for(int i=1;i<=l;i++) h[i]=h[i-1]*233+st[i-1]; for(int i=1;i<=l;i++) { hs=hs*233+st[i-1];//每次都要算 if(l%i!=0) continue;//子串对不上直接跳过 int pd=1; for(int j=1;j<=l&&pd;j+=i) //每一段都比较一下 if(hsh(h,j,j+i-1)!=hs) pd=0; if(pd)//如果配对成功 { printf("%d\n",l/i); //总长除以子串长算数量 break; } } } return 0;//AC } ```