最小表示法(模板) CH1807
思路:将原字符串加倍,一段一段暴力比较,复杂度n*n。通过排除无用比较实现线性求。详见蓝书(算法竞赛指南)P72。
注意:1.以1作为下标起始,应该输入时+1!!(易漏)
2.最小表示法中的while边界是原字符串!!
/* 题意: 判断两个串是否是循环同构串(加倍用KMP) 如果是,找出其最小表示 (模板) */ #include<bits/stdc++.h> using namespace std; #define N 100005 int lena,lenb,nex[N]; char a[N*2],b[N*2]; void get_nex() { nex[1]=nex[0]=0; for(int i=2,j=0;i<=lenb;i++){ while(j>0&&b[i]!=b[j+1]) j=nex[j]; if(b[i]==b[j+1]) j++; nex[i]=j; } } void work() { int k=0,i=1,j=2;//i j 的值要随时保持不一样 while(i<=lena&&j<=lena)//这里应该是原长!!而不是加倍后的长度 { for(k=0;k<=lena&&a[i+k]==a[j+k];k++); if(k==lena) break;//特殊情况:只有一种字符组成 if(a[i+k]>a[j+k]){ i=i+k+1; if(i==j) i++;//i j应该不一样 否则就会把它当特殊情况处理 } else{ j=j+k+1; if(i==j) j++; } } int ans=min(i,j);//最后答案应该从较小的一个开始 for(int kk=ans;kk<=ans+lena-1;kk++) printf("%c",a[kk]); } void solve() { int fl=0; for(int i=1;i<=lena;i++) a[i+lena]=a[i]; for(int i=1,j=0;i<=lena*2;i++){ while(j>0&&(j==lenb||a[i]!=b[j+1])) j=nex[j]; if(a[i]==b[j+1]) j++; //printf("%d\n",j); if(j==lenb){ fl=1; break; } } if(!fl) { printf("No\n"); return ; } printf("Yes\n"); work(); } int main() { scanf("%s%s",a+1,b+1);//一定要记得角标+1!! lena=strlen(a+1),lenb=strlen(b+1); get_nex(); solve(); } /* 2234342423 2423223434 2341 3412 */