题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1692
题意：一个串，每次可以从前面或者后面拽出来一个放到新串头，求最小字典序新串。
朴素的贪心思路是非常简单的，即每次都选头和尾中最小的那个。
如果相同怎么办呢？暴力的话就是判断下一位，直到不同为止，然而复杂度无法保证
考虑我们要的实际上是什么：比较一个前缀串和一个后缀串的字典序，如果都是后缀串显然直接 SA，前缀怎么办呢？
有一个很妙的方法：将原串翻转一遍接在后面，这样后半段就是用后缀串表示的前缀串了。
大小一定在两半串分割之前比较出来，若比较出不来，相等的情况随便选啦
这样的话，对新串求 rank 就可以了。每次不单纯的判断头和尾的字典序，而是判断头在前半后缀的 rank 和尾在后半后缀的 rank。时间复杂度\(O(nlog_n)\)(只会倍增 qwq
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 60010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int t1[N],t2[N],buc[N],sa[N],rk[N],height[N]; int n,top; char s[N],stk[N]; void BuildSA(int m) { int *x=t1,*y=t2; for(int i=0;i<m;i++)buc[i]=0; for(int i=0;i<n;i++)buc[x[i]=s[i]]++; for(int i=1;i<m;i++)buc[i]+=buc[i-1]; for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i; for(int k=1;;k<<=1) { int p=0; for(int i=n-k;i<n;i++)y[p++]=i; for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(int i=0;i<m;i++)buc[i]=0; for(int i=0;i<n;i++)buc[x[y[i]]]++; for(int i=1;i<m;i++)buc[i]+=buc[i-1]; for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i]; swap(x,y); p=1,x[sa[0]]=0; for(int i=1;i<n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p-1:p++; m=p; if(p>=n)break; } for(int i=0;i<n;i++) rk[sa[i]]=i; } int main() { n=read(); for(int i=0;i<n;i++) { char c=getchar(); while(c>'Z'||c<'A')c=getchar(); s[i]=c; } for(int i=0;i<n;i++) s[2*n-1-i]=s[i]; n<<=1,n++; BuildSA(257); n--,n>>=1; int l=0,r=n-1; while(l<=r) { if(rk[l]<rk[2*n-1-r]) stk[++top]=s[l++]; else stk[++top]=s[r--]; } for(int i=1;i<=top;i++) { putchar(stk[i]); if(i%80==0)printf("\n"); } } |
Comments | NOTHING