这题提交的人好少,不会都以为要手写快排吧
我一开始也是这么想的,后来才发现能用sort(蠢死>_<)
不过写都写了还是贴一下吧
我看上面的dalao用的是基数排序(tql%%%)
言归正传,这题要对字符串后缀进行排序
比较两个后缀的时候,我们只需要预处理一下字符串前缀hash,二分求出它们的最长公共前缀,再比较第一位不相等的就行了,复杂度为O(logn)
话说字符串好像不用判越界
(然后套一个sort直接AC,运行时间10s)
然后是快排
我用的是左右指针法
首先设立一个基准数key(我用的是第一个数)
设立两个指针,从右往左找到一个小于key的值,再从左往右找到第一个大于key的值,将它们交换
一般来说是先移动右指针(如果key选的是最后一个数就反过来),不过这里后缀不可能相等,我测了一下都是没问题的
代码还是很好写的
void qsort(ull *a,int l,int r){//天依QwQ(硬核水印)
if(l>=r)return;//判断越界
ull key=a[l];//设立基准数
int i=l,j=r;//双指针
while(i<j){
while(i<j&&cmp(key,a[j]))j--;//移动左右指针(严格地说这里是key小于等于a[j],我写的cmp是小于,不过两个后缀不可能相等)
while(i<j&&cmp(a[i],key))i++;
swap(a[i],a[j]);//交换左右指针对应数值
}//i与j相遇
swap(a[i],key);//插入key值
qsort(a,l,i-1);
qsort(a,i+1,r);
}
然后欢乐TE了……
有一组数据是aaa…aaa(n个a)
记得加一个random_shuffle
运行时间是16s(怎么还慢了)
整个非递归看看会不会快一点
非递归的基本思路就是建一个栈,将左右边界进栈
似乎并没有更快……
最后贴一下完整代码,去掉快排只有31行
(总结:sort永远滴神)
#include<bits/stdc++.h>//by:天依小柠檬
#define N 300009
#define BASE 131
using namespace std;
typedef unsigned long long ull;
string s;
ull H[N],p[N]={1},n,SA[N];
int height(const int&a,const int&b){
int l=0,r=n-max(a,b)+1;
// cout<<a<<" "<<b<<endl;
while(l<r){
int mid=l+r+1>>1;
if(H[a+mid-1]-H[a-1]*p[mid]==H[b+mid-1]-H[b-1]*p[mid])l=mid;
else r=mid-1;
// cout<<mid<<endl;
}
return l;
}
bool cmp(const int&a,const int&b){
int h=height(a,b);
return s[a+h]<s[b+h];
}
void qsort(ull *a,int l,int r){
stack<int> s;
s.push(l);
s.push(r);
while(!s.empty()){
r=s.top();s.pop();
l=s.top();s.pop();//注意入栈顺序和出栈顺序对应
ull key=a[l];//设立基准数
int i=l,j=r;//双指针
while(i<j){
while(i<j&&cmp(a[i],key))i++;
while(i<j&&cmp(key,a[j]))j--;
swap(a[i],a[j]);
}
swap(a[i],key);
if(i-1>l){//判断越界
s.push(l);s.push(i-1);
}
if(i+1<r){
s.push(i+1);s.push(r);
}
}
}
int main(){
cin>>s;s=' '+s;
n=s.size()-1;
for(int i=1;i<=n;i++)p[i]=p[i-1]*BASE,H[i]=H[i-1]*BASE+s[i],SA[i]=i;
// sort(SA+1,SA+n+1,cmp);
qsort(SA,1,n);//自己加个随机化吧~
for(int i=1;i<=n;i++)printf("%d ",SA[i]-1);puts("");
printf("0 ");for(int i=2;i<=n;i++)printf("%d ",height(SA[i],SA[i-1]));
return 0;
}
%%%
%%%