正解:SA
解题报告:
和工艺那题有点儿像鸭,,,反正肯定就都想到倍长然后SA拍个序嘛先
然后就做完了,,,我发现SA的题刷起来特别susi,,,基本上紫题级别的都just一个模板就欧克了最多有一点儿小变化,,,然后有点儿思维难度的就已经是黑题了,,,就刷多点儿SA的题就感觉似乎做了很多紫题的样子,,,但其实思维难度都不大然后代码难度也不高,,,
#include<bits/stdc++.h> using namespace std; #define il inline #define ri register int #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) const int N=200000+10; int n,t[N<<1],sa[N<<1],y[N<<1],x[N<<1]; char ch[N],str[N<<1]; il bool cmp(ri gd,ri gs,ri k){return y[gd]==y[gs] && y[gd+k]==y[gs+k];} il void SA() { ri m=500; rp(i,1,n)++t[x[i]=str[i]]; rp(i,1,m)t[i]+=t[i-1]; my(i,n,1)sa[t[x[i]]--]=i; for(ri k=1;k<=n;k<<=1) { ri p=0; rp(i,1,n)y[i]=0;rp(i,0,m)t[i]=0; rp(i,n-k+1,n)y[++p]=i;rp(i,1,n)if(sa[i]>k)y[++p]=sa[i]-k; rp(i,1,n)++t[x[y[i]]]; rp(i,1,m)t[i]+=t[i-1]; my(i,n,1)sa[t[x[y[i]]]--]=y[i]; swap(x,y); x[sa[1]]=p=1; rp(i,2,n)x[sa[i]]=cmp(sa[i],sa[i-1],k)?p:++p; if(p>=n)break;m=p; } } int main() { freopen("4051.in","r",stdin);freopen("4051.out","w",stdout); scanf("%s",ch+1);ri lth=strlen(ch+1);rp(i,1,lth)str[++n]=ch[i];rp(i,1,lth)str[++n]=ch[i]; SA();rp(i,1,n)if(sa[i]<=lth)printf("%c",str[sa[i]+lth-1]); return 0; }所以放下代码趴!