比较简单的后缀数组应用题。。 首先肯定是贪心选，不同的自不用说，相同的看他后面的字串是否更优秀，这就用到了rank的作用，看两个字串的rank哪一个更小哪一个更优。 求rank的时候直接把字符串加个区分符然后倒过来黏贴一遍，然后直接做就好了。 一般来说后缀数组的题目，一开始要想怎么操作，然后用SA去优化，而不是老是想着用SA怎么做，这样子很容易失了智，啥都想不到 = =
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; char s[N]; int n,m; int b[N],c[N],d[N]; int rank[N],height[N],sa[N]; char ch; inline void read(char &x) { while (ch=getchar(),ch>'Z' || ch<'A') ; x=ch; } inline void getsa(int n,int m) { fo(i,0,m)b[i]=0; fo(i,1,n)b[s[i]]++; fo(i,1,m)b[i]+=b[i-1]; fd(i,n,1)c[b[s[i]]--]=i; int t=0; fo(i,1,n) { if (s[c[i]]!=s[c[i-1]])t++; rank[c[i]]=t; } int j=1; while (j<=n) { fo(i,0,n)b[i]=0; fo(i,1,n)b[rank[i+j]]++; fo(i,1,n)b[i]+=b[i-1]; fd(i,n,1)c[b[rank[i+j]]--]=i; fo(i,0,n)b[i]=0; fo(i,1,n)b[rank[i]]++; fo(i,1,n)b[i]+=b[i-1]; fd(i,n,1)d[b[rank[c[i]]]--]=c[i]; int t=0; fo(i,1,n) { if (rank[d[i]]!=rank[d[i-1]]||rank[d[i]]==rank[d[i-1]]&&rank[d[i]+j]!=rank[d[i-1]+j])t++; c[d[i]]=t; } fo(i,1,n)rank[i]=c[i]; if (t==n)break; j*=2; } } int main() { scanf("%d",&n); fo(i,1,n)read(s[i]),s[i]-=('A'-1); s[n+1]=0; int len=n*2+2; s[len]=0; fo(i,1,n)s[n+1+i]=s[n+1-i]; getsa(len+1,28); int l=1,r=n+2,tot=0; while (l+r<=len) { if (rank[l]<rank[r]) putchar(s[l++]+'A'-1);else putchar(s[r++]+'A'-1); tot++; if (tot%80==0)putchar('\n'),tot=0;; } }