只要求出两个字符串的最小表示，然后就可以判断是否循环同构。
枚举最小表示的开头在哪个位置，然后求出Hash值，如果两个串的Hash值集合有交，那么说明循环同构。
因为串经过压缩，原串的长度很大，不能直接枚举开头。
考虑当开头在某个串$A^k$里某个位置时的性质：
假设$A^k$全在开头，现在考虑挪动一个$A$到结尾。
那么如果挪动之后字典序更小了，那么再挪动一个$A$到结尾，比较条件不变。
因此一旦挪动一个$A$之后字典序变小，那么最小表示一定是将$k-1$个$A$全部挪到结尾。
所以对于一个压缩串$A^k$，只需要在其第一次重复和最后一次重复的部分枚举开头即可。
对于这两部分，Hash值可以直接递推计算，对于中间$k-2$次移动，可以用矩阵快速幂计算。
时间复杂度$O(tk|S|\log|S|)$。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i) for(int i=0;i<2;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>PI;
const int N=30010,S=233,P[2]={1000000007,1000000009};
inline bool check(char x){return x>='a'&&x<='z';}
struct String{
char s[N];ll tot;
int cnt,n,len[N],w[N],st[N],en[N];
void read(){
static char a[N];
scanf("%s",a);
int l=strlen(a),i,j,k;
cnt=n=tot=0;
for(i=0;i<l;){
if(check(a[i])){
st[++n]=cnt+1;
for(j=i;j<l&&check(a[j]);j++);
for(k=i;k<j;k++)s[++cnt]=a[k];
en[n]=cnt;
len[n]=en[n]-st[n]+1;
w[n]=1;
tot+=len[n]*w[n];
i=j;
}else{
st[++n]=cnt+1;
for(j=++i;j<l&&check(a[j]);j++);
for(k=i;k<j;k++)s[++cnt]=a[k];
en[n]=cnt;
len[n]=en[n]-st[n]+1;
w[n]=0;
for(j++;j<l&&a[j]>='0'&&a[j]<='9';j++)w[n]=w[n]*10+a[j]-'0';
tot+=len[n]*w[n];
i=j;
}
}
}
void write(){
int i,j;
printf("%d %lld\n",n,tot);
for(i=1;i<=n;i++){
for(j=st[i];j<=en[i];j++)putchar(s[j]);
printf(" %d %d\n",len[i],w[i]);
}
}
}A,B;
namespace Hash{
char s[N];ll tot;
int cnt,n,i,j,k,x,y,len[N],w[N],st[N],en[N],f[N][2],g[2],mo;
struct mat{
int v[2][2];
mat(){}
mat operator*(const mat&b){
mat c;
rep(i)rep(j)c.v[i][j]=0;
rep(i)rep(j)rep(k)c.v[i][j]=(1LL*v[i][k]*b.v[k][j]+c.v[i][j])%mo;
return c;
}
};
inline int pow(int a,ll b,int P){int t=1;for(;b;b>>=1LL,a=1LL*a*a%P)if(b&1LL)t=1LL*t*a%P;return t;}
inline int cal(int f,int l,int w,int P){
mo=P;
mat A,B;
rep(i)rep(j)A.v[i][j]=B.v[i][j]=0;
B.v[1][0]=f;
A.v[0][0]=A.v[0][1]=1,A.v[1][1]=pow(S,l,P);
for(;w;w>>=1,A=A*A)if(w&1)B=A*B;
return B.v[0][0];
}
void solve(PI*v,int&cv,const String&p,ll L){
cv=cnt=n=0,tot=L;
for(i=1;i<=p.n;i++){
x=min(L/p.len[i],1LL*p.w[i]);
if(x){
st[++n]=cnt+1;
for(j=p.st[i];j<=p.en[i];j++)s[++cnt]=p.s[j];
en[n]=cnt;
len[n]=en[n]-st[n]+1;
w[n]=x;
}
L-=x*p.len[i];
if(!L)break;
if(L<p.len[i]&&x<p.w[i]){
st[++n]=cnt+1;
for(j=p.st[i];j<p.st[i]+L;j++)s[++cnt]=p.s[j];
en[n]=cnt;
len[n]=L;
w[n]=1;
break;
}
}
for(i=0;i<2;i++)g[i]=0;
for(i=1;i<=n;i++){
for(j=0;j<2;j++)f[i][j]=0;
for(j=st[i];j<=en[i];j++)for(k=0;k<2;k++)f[i][k]=(1LL*f[i][k]*S+s[j])%P[k];
for(j=0;j<2;j++)g[j]=(1LL*g[j]*pow(S,len[i]*w[i],P[j])+cal(f[i][j],len[i],w[i],P[j]))%P[j];
}
for(i=1;i<=n;i++){
for(j=st[i];j<=en[i];j++){
v[++cv]=PI(g[0],g[1]);
for(k=0;k<2;k++){
g[k]=(g[k]-1LL*s[j]*pow(S,tot-1,P[k])%P[k]+P[k])%P[k];
g[k]=(1LL*g[k]*S+s[j])%P[k];
}
}
if(w[i]==1)continue;
for(j=0;j<2;j++){
x=len[i]*(w[i]-2);
y=cal(f[i][j],len[i],w[i]-2,P[j]);
g[j]=(g[j]-1LL*y*pow(S,tot-x,P[j])%P[j]+P[j])%P[j];
g[j]=(1LL*g[j]*pow(S,x,P[j])+y)%P[j];
}
for(j=st[i];j<=en[i];j++){
v[++cv]=PI(g[0],g[1]);
for(k=0;k<2;k++){
g[k]=(g[k]-1LL*s[j]*pow(S,tot-1,P[k])%P[k]+P[k])%P[k];
g[k]=(1LL*g[k]*S+s[j])%P[k];
}
}
}
}
}
int T,C,k,o,ans,ca,cb,i,j;PI a[N],b[N];
int main(){
scanf("%d",&T);
for(C=1;C<=T;C++){
A.read();
scanf("%d",&k);ans=0;
for(o=1;o<=k;o++){
B.read();
Hash::solve(a,ca,A,B.tot);
Hash::solve(b,cb,B,B.tot);
sort(a+1,a+ca+1),sort(b+1,b+cb+1);
for(i=j=1;i<=ca&&j<=cb;){
if(a[i]<b[j])i++;
else if(a[i]>b[j])j++;
else{
ans+=o*o;
break;
}
}
}
printf("Case #%d: %d\n",C,ans);
}
return 0;
}