后缀数组-另辟蹊径

参考资料

后缀数组新手向入门 by xMinh

后缀数组——强大的字符串处理工具 by laeva

后缀数组 by hyfhaha

2012年noi冬令营陈立杰讲稿

罗穗骞《后缀数组——处理字符串问题的有力工具》

1. 朴素算法

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef unsigned long long ULL;
using namespace std;
const int N=1e6+5;
char a[N];
int n;
int sa[N];
inline bool rule(int p,int q)
{
	for(int i=0;p+i<=n&&q+i<=n;i++) {
		if(a[p+i]!=a[q+i])
			return a[p+i]<a[q+i];
	}
	return p>q;
}
int main()
{
//	freopen("1.in","r",stdin);
	int i;
	scanf("%s",a+1);
	n=strlen(a+1);
	for(i=1;i<=n;i++) sa[i]=i;
	sort(sa+1,sa+n+1,rule);
	for(i=1;i<=n;i++) 
		printf("%d ",sa[i]);
	return 0;
}

2 . Hash+binary

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=1e6+5;
const ULL P=131;
char a[N];
int n;
int sa[N];
ULL h[N],POW[N];
inline ULL get(int l,int r)
{
	return h[r]-h[l-1]*POW[r-l+1];
}
inline bool rule(int p,int q)
{
	int L=-1,R=min(n-p,n-q)+1,mid;
	while(L+1<R) {
		mid=(L+R)>>1;
		if(get(p,p+mid)==get(q,q+mid)) L=mid;
		else R=mid;
	}
	p=p+L+1; q=q+L+1;
	if(p==n+1||q==n+1) return (p==n+1);
	else return a[p]<a[q];
}
int main()
{
//	freopen("1.in","r",stdin);
	int i;
	scanf("%s",a+1);
	n=strlen(a+1);
	POW[0]=1;
	for(i=1;i<=n;i++) {
		sa[i]=i;
		h[i]=h[i-1]*P+a[i];
		POW[i]=POW[i-1]*P;
	}
	sort(sa+1,sa+n+1,rule);
	for(i=1;i<=n;i++) 
		printf("%d ",sa[i]);
	return 0;
}

3. Hash+倍增

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=1e6+5;
const ULL P=131;
char a[N];
int n;
int sa[N];
ULL h[N],POW[N];
inline ULL get(int l,int r)
{
	return h[r]-h[l-1]*POW[r-l+1];
}
inline bool rule(int p,int q)
{
	int base=1;
	while(base>0) {
		if(p+base-1>n||q+base-1>n) base>>=1;
		else if(get(p,p+base-1)==get(q,q+base-1)) {
			p+=base; q+=base;
			base<<=1;
		}
		else base>>=1;
	}
	if(p==n+1||q==n+1) return (p==n+1);
	else return a[p]<a[q];
}
void print(int x)
{
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
int main()
{
//	freopen("1.in","r",stdin);
	int i;
	scanf("%s",a+1);
	n=strlen(a+1);
	POW[0]=1;
	for(i=1;i<=n;i++) {
		sa[i]=i;
		h[i]=h[i-1]*P+a[i];
		POW[i]=POW[i-1]*P;
	}
	sort(sa+1,sa+n+1,rule);
	for(i=1;i<=n;i++) 
		print(sa[i]),putchar(' ');
	return 0;
}

倍增在随机数据下运行效率很高，但常数较大。

二分在构造数据下会快不少。