后缀排序

link

挖个坑。SAM这种坑B玩意我寒假之前一定要搞懂。但现在而今眼目下，我的功力还不够，搞后缀自动机很有点困难，毕竟我连AC自动机都不会……

但后缀数组相对而言简单一些。学的时候并不知道有什么用，但后来发现太有趣了。首先入门题，后缀排序。

这里使用了两个东西，一个是基数排序，一个是倍增思想。基数排序可以理解为对一个二元组进行桶排，倍增思想不多说。整个排序过程就是对排序长度进行倍增的过程，不难想到它的复杂度是\(O(NlogN)\)的。实现上难度不大。

我的写法比较笨但比较清晰，只是跑得慢是慢了点。

#include
#include
//#define zczc
using namespace std;
const int N=1000010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}wh*=f;return;
}
inline int min(int s1,int s2){return s1m?0:a[i+n];work();maxn=0;
		for(int i=1;i<=m;i++)a[s[i].id]=(i==1||s[i].x!=s[i-1].x||s[i].y!=s[i-1].y)?++maxn:maxn;
	}
	for(int i=1;i<=m;i++)printf("%d ",s[i].id);return 0;
}