最小表示法，这里用后缀自动机实现。 刚刚学了后缀自动机，懵逼中。 ps：纯属为了练习后缀自动机，字符串最小表示法的专门算法比这快很多。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int maxn=3001000;char s[maxn*2];int n;struct sam{ int a[maxn][30],mx[maxn],fa[maxn],last,cnt; sam(){ last=++cnt; } void insert(int c) { int p=last,np=last=++cnt;mx[np]=mx[p]+1; while(p&&!a[p][c]) a[p][c]=np,p=fa[p]; if(!p) fa[np]=1; else { int q=a[p][c]; if(mx[p]+1==mx[q]) fa[np]=q; else { int nq=++cnt;mx[nq]=mx[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q) a[p][c]=nq;p=fa[p]; } } }}SAM;int main(){ freopen("MinRePResentations.in","r",stdin); freopen("MinRepresentations.out","w",stdout); scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++) s[i+n]=s[i]; for(int i=1;i<=2*n;i++) SAM.insert(s[i]-'a'); for (int i=1,p=1;i<=n;i++) { for (int j=0;j<26;j++) if(SAM.a[p][j]) { putchar('a'+j); p=SAM.a[p][j]; break; } } puts(""); return 0;}/*10QQqqaabaaa*/新闻热点
疑难解答
