HDU 5769 Substring（后缀数组）

题意

求字符串 (S) 本质不同且一定包含字符 (X) 的子串个数。

(1 leq |S| leq 10^5)

思路

求一个长度为 (n) 的串 (S) 本质不同的子串个数可以使用公式 (displaystylesum_{i=1}^{n} n-sa[i]+1-H[i]) ，其中 (H[0]=1)。

这个公式是比较好证的。后缀的前缀就是子串，我们分析每个后缀有多少个对答案有贡献的前缀，(n-sa[i]+1) 表示所有前缀的个数， (H[i]) 即 ( ext{lcp}(sa[i],sa[i-1])) ，表示前面出现过重复的前缀个数，减掉即可。

那有了一个出现 (X) 的限制后，这样分析仍然可行。限制增加了出现 (X)，那预处理出每个位置往后的第一个 (X)（本身也可以）的位置 (nxt) ，然后把要减去的值改成 (max(H[i],nxt[sa[i]]-sa[i])) 即可。

代码

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=1e5+5;
int sa[N],rk[N],H[N],tmp[3][N];
char s[N],str[N];
int nxt[N];
char X;
int n;

void get_SA(char *str,int n,int m)
{
	int *x=tmp[0],*y=tmp[1],*c=tmp[2];
	x[n+1]=y[n+1]=0;
	FOR(i,1,m)c[i]=0;
	FOR(i,1,n)c[x[i]=s[i]]++;
	FOR(i,2,m)c[i]+=c[i-1];
	DOR(i,n,1)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int p=0;
		FOR(i,n-k+1,n)y[++p]=i;
		FOR(i,1,n)if(sa[i]>k)y[++p]=sa[i]-k;
		FOR(i,1,m)c[i]=0;
		FOR(i,1,n)c[x[y[i]]]++;
		FOR(i,2,m)c[i]+=c[i-1];
		DOR(i,n,1)sa[c[x[y[i]]]--]=y[i];
		std::swap(x,y);
		p=x[sa[1]]=1;
		FOR(i,2,n)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
		if(n==p)break;
		m=p;
	}
	FOR(i,1,n)rk[sa[i]]=i;
	int k=0;
	H[1]=0;
	FOR(i,1,n)
	{
		if(k)k--;
		if(rk[i]==1)continue;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
		H[rk[i]]=k;
	}
}

ll query()
{
	ll ans=0;
	FOR(i,1,n)ans+=n-sa[i]+1-std::max(H[i],nxt[sa[i]]-sa[i]);
	return ans;
}

int main()
{
	int T;
	scanf("%d",&T);
	FOR(Ti,1,T)
	{
		scanf(" %c%s",&X,s+1);
		n=strlen(s+1);
		get_SA(s,n,256);
		FOR(i,1,n)
		{
			if(s[i]==X)nxt[i]=i;
			else nxt[i]=n+1;
		}
		DOR(i,n-1,1)chk_min(nxt[i],nxt[i+1]);
		printf("Case #%d: %lld
",Ti,query());
	}
	return 0;
}