spoj705.cpp

spoj705 后缀数组 里面有后缀数组的模板 在spoj上提交正确

#include <iostream> 
#include <cstring> 
#include <algorithm> 
using namespace std; 

typedef long long llong;
#define Min(a,b) (a)<(b)?(a):(b) 
#define Max(a,b) (a)>(b)?(a):(b) 
const int N = 50010;
const int M = 128;
int n; 
char s[N]; 
int cnt[N], mem[4][N], *rank, *nrank, *sa, *nsa, h[N]; 
// lcp[i][j]: longest commen prefix ( suffix(sa[k+1]), suffix(sa[k]) ) j <= k < j+2^i 

void radix_sort() 
{ 
	int i, j, k; 
	rank = mem[0]; 
	nrank = mem[1]; 
	sa = mem[2]; 
	nsa = mem[3]; 
	for(i = 1; i < M; i++) cnt[i] =0;
	for(i = 0; i < n; i++) cnt[s[i]]++; 
	for(i = 1; i < M; i++) cnt[i] += cnt[i-1]; 
	for(i = n-1; i >= 0; i--) sa[--cnt[s[i]]] = i;
	for(i = 0; i < n; i++) rank[i]=0;
	for(i=1; i < n; i++) 
	{ 
		rank[sa[i]] = rank[sa[i-1]]; 
		if(s[sa[i]]!=s[sa[i-1]]) rank[sa[i]]++; 
	} 
	for(k = 1; k<n && rank[sa[n-1]] < n-1; k*=2) 
	{ 
		for(i = 0; i < n; i++) cnt[rank[sa[i]]] = i+1; 
		for(i = n-1; i >= 0; i--) if(sa[i]-k>=0) 
			nsa[--cnt[rank[sa[i]-k]]] = sa[i]-k; 
		for(i = n-k; i < n; i++) nsa[--cnt[rank[i]]] = i; 
		for(nrank[nsa[0]]=0, i=1; i < n; i++) 
		{ 
			nrank[nsa[i]] = nrank[nsa[i-1]]; 
			if(rank[nsa[i]] != rank[nsa[i-1]] 
				|| rank[nsa[i]+k] != rank[nsa[i-1]+k]) 
				nrank[nsa[i]]++; 
		} 
		swap(rank, nrank); 
		swap(sa, nsa); 
	} 
} 

void get_lcp_rmq() 
{ 
	int i, j, k; 
	for(i=0; i<n; i++) h[i]=0;
	for(i=0,k=0; i<n; i++) 
	{ 
		if(rank[i]==n-1) h[rank[i]]=k=0; 
		else { 
			if(k>0) k--; 
			j = sa[rank[i]+1]; 
			for(;s[i+k]==s[j+k]&&(i+k<n&&j+k<n);k++) ; 
			h[rank[i]]=k;
		}
	}
	for(i=0; i<n; i++) cout<<" "<<h[i]<<endl;
} 

int main()
{
	llong cases,sum,i;
	scanf("%lld",&cases);getchar();
	while(cases--) {
		//scanf("%s",s);
		gets(s);
		n = strlen(s); s[n++]=0;
		radix_sort();  
	 	get_lcp_rmq();
		sum=(llong)n*(n+1)/2;
		for(i=0;i<n;i++) sum=sum-1-h[i];
		printf("%lld\n",sum);
	}
	return 0;
}