后缀数组.txt

后缀数组的资料在国内还是少有的

//网上找的，别人的。
#include<iostream>
#include<cmath>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=110000;
char s[maxn];
int len,k;
int sa[maxn],rank[maxn],rank2[maxn],h[maxn],height[maxn];

int *d[18][maxn];
inline int *min(int *a,int *b)
{
	if(*a<*b)return a;
	else return b;
}
void make_RMQ(int n)
{
	int i,j;
	for(i=1;i<=n;i++)   d[0][i]=&height[i];  
	for(j=1;j<=int(log(n+0.)/log(2.));j++)
		for(i=1;i+(1<<j)-1<=n;i++)
			d[j][i]=min(d[j-1][i],d[j-1][i+(1<<(j-1))]);
	return ;
}
int *RMQ(int i,int j)
{
	int k=int(log(j-i+1.)/log(2.));
	return min(d[k][i],d[k][j-(1<<k)+1]);
}
bool comp1(const int&a,const int&b)
{
	return s[a]<s[b];
}
bool comp(const int&a,const int&b)
{
	if(rank[a]==rank[b])return rank[a+k]<rank[b+k];
	return rank[a]<rank[b];
} 
bool comp2(const int&a,const int&b)
{
	if(rank2[a]==rank2[b])return rank2[a+k]<rank2[b+k];
	return rank2[a]<rank2[b];
} 
void make_suffix(char s[])
{
	s[0]='$';
	len=strlen(s+1);
	s[len+1]='$';
	int i,j,a,b,n=len;
	for(i=1;i<=n;i++)sa[i]=i;
	sort(sa+1,sa+1+n,comp1);
	for(i=1;i<=n;i++)
	{
		if(s[sa[i]]==s[sa[i-1]])
			rank[sa[i]]=rank[sa[i-1]];              
		else rank[sa[i]]=i;
	}

	for(k=1;k<n;k<<=1)
	{
		sort(sa+1,sa+1+n,comp);
		for(i=1;i<=n;i++)
		{
			if(rank[sa[i]]==rank[sa[i-1]] && rank[sa[i]+k]==rank[sa[i-1]+k])
				rank2[sa[i]]=rank2[sa[i-1]];
			else rank2[sa[i]]=i;
		}
		k<<=1;
		sort(sa+1,sa+1+n,comp2);
		for(i=1;i<=n;i++)
		{
			if(rank2[sa[i]]==rank2[sa[i-1]]&&rank2[sa[i]+k]==rank2[sa[i-1]+k])
				rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=i;
		}
	}
	for(i=1;i<=n;i++)
	{
		a=i;b=sa[rank[i]-1];
		if(rank[i]==1)h[i]=0;
		else if(i==1||h[i-1]<=1)
		{
			for(j=0;;j++)
				if(s[a+j]!=s[b+j])break;
			h[i]=j;
		}
		else
		{
			for(j=h[i-1]-1;;j++)
				if(s[a+j]!=s[b+j])break;
			h[i]=j;
		}
	}
	for(i=1;i<=n;i++)height[i]=h[sa[i]];
	make_RMQ(len);
}
int lcp(int i,int j)
{
	i=rank[i]; j=rank[j];
	if(i>j)swap(i,j);
	if(i==j)return len-sa[i]+1;
	return *RMQ(i+1,j);
}
int main()
{
//	freopen("in.cpp","r",stdin);freopen("out.cpp","w",stdout);
	int i;
	scanf("%s",s+1);
	make_suffix(s);
	for(i=1;i<=len;i++)printf("%d ",sa[i]);
	cout<<endl;
	for(i=1;i<=len;i++)printf("%d ",rank[i]);
	cout<<endl;
	for(i=1;i<=len;i++)printf("%d ",h[i]);
	cout<<endl;
	for(i=1;i<=len;i++)printf("%d ",height[i]);
	cout<<endl;
	cout<<lcp(1,5)<<endl;
	printf("%d\n",'a');
	return 0;
}


//下面是自己写的，正确性还不知道。

#include<iostream>
#include<cmath>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 10010
#define MIN(a,b) (a<b)?a:b
char s[MAX],k;
int sa[MAX],sa2[MAX],rank[MAX],rank2[MAX],n,h[MAX],height[MAX],len;
int d[18][MAX];

bool cmp1(int a,int b)
{
	return s[a]<s[b];
}

bool cmp2(int a, int b)
{
	if(rank[a] == rank[b])return rank[a+k]<rank[b+k];
	else return rank[a] < rank[b];
}
void make_suffix()
{
	int i,j;
	len = strlen(s+1);
	n=len; 
	s[0] = '$';
	s[len+1] = '$';
	for(i=1;i<=len;i++) sa[i] = i;
	sort(sa+1,sa+1+len,cmp1);
	for(i=1; i<=len;i++)
	{
		if(s[ sa[i] ] == s[ sa[i-1] ])
			rank[ sa[i] ] = rank[ sa[i-1] ];
		else rank[ sa[i] ] = i;
	}
	for(k=1; k<=len ;k = k<<1)
	{
		sort(sa+1, sa+1+len, cmp2);
		for(i=1;i<=len;i++)
		{
			if(i>1 && rank[sa[i]]==rank[sa[i-1]] && rank[sa[i]+k] == rank[sa[i-1]+k])
				rank2[sa[i]] = rank2[sa[i-1]];
			else rank2[sa[i]] = i;
		}
		memcpy(rank,rank2,(len+1)*sizeof(int));
	}
	for(i=1;i<=len;i++) //求出h[i]
	{
		int a,b;
		a=i; b=sa[rank[i]-1];
		if(rank[i]==1) h[i]=0;
		else if(i==1 || h[i-1]<=1)
		{
			for(j=0;;j++)
				if(s[a+j]!=s[b+j])break;
			h[i]=j;
		}
		else
		{
			for(j=h[i-1]-1;;j++)
				if(s[a+j]!=s[b+j])break;
			h[i]=j;
		}
	}
	for(i=1;i<=len;i++)
		height[rank[i]] = h[i]; //或者 height[i] = h[sa[i]] 

}

void make_rmq()
{
	int i,k;
	for(i=1;i<=len;i++)
		d[0][i] = height[i];
	for(k=1;(1<<k)<=len;k++)
	{
		for(i=1;i+(1<<k)-1 <= len;i++)
		{
			d[k][i] = MIN(d[k-1][i],d[k-1][i+1<<(k-1)]);
		}
	}
}

int lcs(int i,int j) //i,j 都从1开始计数的
{
	i=rank[i]; j=rank[j];
	if(i==j)return len-sa[i]+1;
	if(i>j){int temp=i; i=j; j=temp;}
	int m = 0;
	while ((1<<m)<=(j-i)) m++;
	m--;
	return MIN(d[m][i+1], d[m][j-(1<<m)+1]); //d[m][i+1]之所以要加1,
}                                               //因为，LCP(i,j)=min{height[k]|i+1≤k≤j}

int main()
{
	int a,b;
	scanf("%s",s+1);
	make_suffix();
	make_rmq();
	scanf("%d %d",&a,&b);
	printf("%d",lcs(a,b));
}