后缀数组的两种算法_合并两个有序数组

求一个字串的不同字串有多少个。问不同的字串有多少个，即问对于每一个后缀，它的所有前缀中，与其他后缀的前缀不同的有几个。解法是按rank将后缀一个个加进来，那么每加进一个后缀，将会增加n-sa[i]+1个前缀，但这些前缀中，有一些是之前出现过的，之前出现过的个数就是i与之前加进来的所有后缀的最长公共前缀的长度，很显然，就是height[i]。那么每次能获得的不同的字串的个数就是n-sa[i]+1-height[i]。

对于区间[l,r]其实也是一样的。

首先将[l,r]区间内的后缀筛出来，按rank排序。每加进来一个后缀，将会增加r-sa[i]+1个前缀，重复的前缀依然是与之前排名的后缀的最长公共前缀长度。这里就不是前一个了，因为前一个后缀可能被区间截断。

考虑递推的思想。

令temp为上一个后缀与之前所有后缀的最长公共前缀长度。

k为当前后缀与上一个后缀的最长公共前缀。

如果k<temp，那么当前后缀与之前所有后缀的最长公共前缀长度就为k。

否则，当前后缀与之前所有后缀的最长公共前缀长度至少为temp，如果在前一个后缀的范围内可以有更长的前缀，则更新为MIN(k,前一个后缀的长度)。

附代码喵：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)
char s[2020];
int ans;
int sa[2020],wa[2020],c[2020],wb[2020];
int ran[2020],height[2020];
int dp[2020][20];
int idx(char c)
{
	if(c==0)return 0;
	return c-'a'+1;
}
bool cmp(int *r,int a,int b,int k)
{
	return r[a]==r[b]&&r[a+k]==r[b+k];
}
void build_sa(int m,int n)
{
	int *x=wa,*y=wb,*t;
	for(int i=0;i<m;i++)c[i]=0;
	for(int i=0;i<n;i++)c[x[i]=idx(s[i])]++;
	for(int i=1;i<m;i++)c[i]+=c[i-1];
	for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
	for(int k=1;k<=n;k*=2){
		int p=0;
		for(int i=n-k;i<n;i++)y[p++]=i;
		for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;

		for(int i=0;i<m;i++)c[i]=0;
		for(int i=0;i<n;i++)c[x[y[i]]]++;
		for(int i=1;i<m;i++)c[i]+=c[i-1];
		for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];

		t=x;x=y;y=t;
		x[sa[0]]=0;p=1;
		for(int i=1;i<n;i++)
		{
			x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?p-1:p++;
		}
		if(p>=n)break;
		m=p;
	}
}
void calheight(int n)
{
	for(int i=0;i<n;i++)ran[sa[i]]=i;
	int k=0;
	for(int i=0;i<n;i++)
	{
		if(k)k--;//必须在前面
		if(ran[i]==0)continue;
		int j=sa[ran[i]-1];
		while(s[i+k]==s[j+k])k++;
		height[ran[i]]=k;
	}
}
void initrmq(int n)
{
	for(int i=1;i<n;i++)dp[i][0]=height[i];
	for(int j=1;(1<<j)<n;j++){
			for(int i=1;i+(1<<j)-1<n;i++)
	{
			dp[i][j]=MIN(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
}
int lcp(int l,int r)
{
	if(r<l)swap(l,r);
	l++;
	int k=0;
	while((1<<(k+1))<=r-l+1)k++;
	return MIN(dp[l][k],dp[r-(1<<k)+1][k]);
}
int substring(int l,int r,int n)
{
	int tmp,add;
	l--;r--;
	vector<int>pos;
	for(int i=0;i<n;i++)//pos按后缀排名顺序存放了（l，r）的后缀
	{
		if(sa[i]>=l&&sa[i]<=r)pos.push_back(sa[i]);
	}
	int sum=r-pos[0]+1;//第一个字符串长度
	int temp=sum;
	for(int i=1;i<pos.size();i++)
	{
		int len=r+1-pos[i];//当前字符串长度
		int k=lcp(ran[pos[i]],ran[pos[i-1]]);
		temp= MIN( temp , k ) ;//temp表示上一个字符串与之前所有字符串的最长公共前缀长度,可能大于区间后缀长度
		 //如果当前字符串与上一个字符串的最长公共前缀k小于temp，那么与之前所有也会小于k，当前字符串与之前所有字符串的最长公共前缀长度就为k
        //如果大于temp，首先temp肯定是有效的，再判断是否在上个后缀与当前后缀能否在有效范围内增公共前缀长度。
		temp = MAX ( temp , MIN ( k ,r-pos[i-1]+1)) ;
        sum+= len-MIN ( temp , len ); //产生新字符串则更新。
	}
	return sum;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s);
		int n=strlen(s);
		build_sa(27,n+1);calheight(n+1);
		initrmq(n+1);
		int Q;
		scanf("%d",&Q);
		while(Q--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			int ans=substring(l,r,n+1);
			printf("%d\n",ans);
		}
	}
	return 0;
}

今天的文章后缀数组的两种算法_合并两个有序数组分享到此就结束了，感谢您的阅读。