洛谷2408不同字串个数/SPOJ 694/705 （后缀数组SA）

真是一个三倍经验好题啊。

我们来观察这个题目，首先如果直接整体计算，怕是不太好计算。

首先，我们可以将每个子串都看成一个后缀的的前缀。那我们就可以考虑一个一个后缀来计算了。

为了方便起见，我们选择按照字典序来一次插入每个后缀，然后每次考虑当前后缀会产生的新串和与之前插入的串重复的串（这里之所以可以这么考虑，是因为如果他会对后面的串产生重复的话，那么会在后面那个串加入的时候计算的）

那么我们考虑，一个排名为(i)的后缀，插入之后不考虑重复的话，会新增多少个子串呢？
不难发现是(n-sa[i]+1)个（注意后缀的位置编号是从前开始，而后缀的贡献是后面的子串个数。

那么重复的该怎么计算呢？

我们发现重复的部分实际是当前这个后缀和之前的后缀的(lcp)部分会重复，而且应该是最大的(lcp) （如果取小的会算少，直接求sum会算多）。

而有一个比较经典的性质就是，在字典序(1到i)中与(i)的(lcp)长度最长的，一定是(i-1)，这里有两种理解方式，一个是越远差距越大，另一种是越靠前，取(min)的范围越大，(min)就会可能越小

那么枚举+计算，记得开(long long)就三倍经验辣

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk makr_pair
#define ll long long
using namespace std;
inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}
const int maxn = 2e5+1e2;
int rk[maxn],sa[maxn];
int wb[maxn];
int tmp[maxn];
char a[maxn];
int n;
int h[maxn],height[maxn];
void getsa()
{
	int *x=rk,*y=tmp;
	int s=128;
	int p=0;
	for (int i=1;i<=n;i++) x[i]=a[i],y[i]=i;
	for (int i=1;i<=s;i++) wb[i]=0;
	for (int i=1;i<=n;i++) wb[x[y[i]]]++;
	for (int i=1;i<=s;i++) wb[i]+=wb[i-1];
	for (int i=n;i>=1;i--) sa[wb[x[y[i]]]--]=y[i];
	for (int j=1;p<n;j<<=1)
	{
		p=0;
		for (int i=n-j+1;i<=n;i++) y[++p]=i;
		for (int i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
		for (int i=1;i<=s;i++) wb[i]=0;
		for (int i=1;i<=n;i++) wb[x[y[i]]]++;
		for (int i=1;i<=s;i++) wb[i]+=wb[i-1];
		for (int i=n;i>=1;i--) sa[wb[x[y[i]]]--]=y[i];
		swap(x,y);
		p=1;
		x[sa[1]]=1;
		for (int i=2;i<=n;i++)
		  x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]) ? p : ++p;
		s=p;
	}
	for (int i=1;i<=n;i++) rk[sa[i]]=i;
	h[0]=0;
	for (int i=1;i<=n;i++)
	{
	  h[i]=max(h[i-1]-1,0);
	  while(i+h[i]<=n && sa[rk[i]-1]+h[i]<=n && a[i+h[i]]==a[sa[rk[i]-1]+h[i]]) h[i]++;
	}
	for (int i=1;i<=n;i++) height[i]=h[sa[i]];
} 
int t;
void init()
{
	memset(wb,0,sizeof(wb));
	memset(rk,0,sizeof(rk));
	memset(sa,0,sizeof(sa));
	memset(tmp,0,sizeof(tmp));
	memset(h,0,sizeof(h));
	memset(height,0,sizeof(height));
}
int main()
{
  //cin>>t;
  //while (t--)
  //{
     n=read();
  	 init();
  	 scanf("%s",a+1);
  	 getsa();
  	 long long ans=0;
  	 for (int i=1;i<=n;i++)
  	 {
  	 	ans=ans+(long long)(n-sa[i]+1)-(long long)h[i];//这里可以理解成我们顺着字典序的顺序，加入每个后缀，将子串看成后缀的前缀
		// 而每次加入会产生新的n-sa[i]+1个字串，其中重复的就是和之前的子串的某些lcp，而字典序上，在这个串前面，与某个串lcp最长的应该是i-1那个串（这里可以理解成越往前差距越大） 
	   }
	   cout<<ans<<"
";
 // }
  return 0;
}

洛谷2408不同字串个数/SPOJ 694/705 （后缀数组SA）

相关推荐