跟BZOJ 4278: [ONTAK2015]Tasowanie一模一样
SA的做法就是把原串倒过来接在原串后面,做后缀数组,就能够比较每个前缀和后缀谁的字典序小了.
Hash二分也可以.
CODE(SA)
#include
using namespace std;
char cb[1#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1templateinline void read(T &res) {
char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 60005;
int s[MAXN];
int x[MAXN], y[MAXN], c[MAXN], rk[MAXN], sa[MAXN];
inline void Get_Sa(int n, int m) {
for(int i = 1; i for(int i = 2; i for(int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for(int k = 1; k int p = 0;
for(int i = n-k+1; i for(int i = 1; i k) y[++p] = sa[i]-k;
for(int i = 1; i for(int i = 1; i for(int i = 2; i for(int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
x[sa[1]] = p = 1;
for(int i = 2; i x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? p : ++p;
if((m=p) == n) break;
}
for(int i = 1; i }
int n;
int main() {
read(n); char ch;
for(int i = 1; i while(!isalpha(ch=getchar()));
s[i] = ch-'A'+1;
}
for(int i = 1; i Get_Sa(n int l = 1, r = n, tot = 0;
while(l if(rk[l] else { putchar(s[r--]+'A'-1); if(++tot == 80) tot = 0, putchar('n'); }
}
CODE(Hash)
从学长那里搬运来的代码(跑得比后缀数组快)
#include
#include
#include
#include
#define ull unsigned int
using namespace std;
const int maxn=30003;
char s[maxn];
ull pre[maxn],jc[maxn],val1,val2,pre1[maxn];
short i,j,k,n,m,l,r,mid,len,L,R;
inline short getlen(){
if(s[L]!=s[R])return 0;
l=1;r=R-L+1;
if(pre[L+r-1]-pre[L-1]*jc[r]==pre1[R-r+1]-pre1[R+1]*jc[r])return r;r--;
while(lmid=(l+r+1)>>1;
val1=pre[L+mid-1]-pre[L-1]*jc[mid];
val2=pre1[R-mid+1]-pre1[R+1]*jc[mid];
if(val1!=val2)r=mid-1;else l=mid;
if(s[L+l]!=s[R-l])return l;
}
return l;
}
inline bool bigger(){
if(s[L]!=s[R])return s[L]>s[R];
len=getlen();
if(len==R-L+1)return 1;
else return s[L+len]>s[R-len];
}
int main(){
scanf("%d",&n);
for(i=1;i'Z';s[i]=getchar());
jc[0]=1;for(i=1;i for(i=1;i for(i=n;i;i--)pre1[i]=pre1[i+1]*107+(ull)s[i]-'A';
L=1;R=n;
for(i=1;i putchar(s[R--]);
if(i%80==0)putchar('n');
}else {putchar(s[L++]);if(i%80==0)putchar('n');}
return 0;
}