hdu5769 Substring

除草、切了道水题

给定一个字符串和一个字符，求包含该字符的本质不同的字串个数

sa上对height和字符位置取个max加加就没了

#include<bits/stdc++.h>
#define rank _rank
using namespace std;
const int maxn=1e5+5;

int a[maxn],sa[maxn],rank[maxn],height[maxn];
void build_sa(int n){
	static int x[maxn],y[maxn],c[maxn];
	int m=26,k=1;
	memset(c,0,sizeof(*c)*(m+1));
	for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
	for(int i=1;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i;i--)sa]--]=i;
	for(;k<=n;k<<=1){
		int tot=k;
		for(int i=n-k+1;i<=n;i++)y[i-n+k]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>k)y[++tot]=sa[i]-k;
		memset(c,0,sizeof(*c)*(m+1));
		for(int i=1;i<=n;i++)c[x[i]]++;
		for(int i=1;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i;i--)sa]]--]=y[i];
		for(int i=1;i<=n;i++)y[i]=x[i];
		tot=1;x[sa[1]]=1;
		for(int i=2;i<=n;i++){
			if(max(sa[i],sa[i-1])+k>n
					||y[sa[i]]!=y[sa[i-1]]
					||y[sa[i]+k]!=y[sa[i-1]+k])
				tot++;
			x[sa[i]]=tot;
		}
		if(tot==n)break;else m=tot;
	}
	for(int i=1;i<=n;i++)rank[sa[i]]=i;
	for(int i=1;i<=n;i++){
		height[rank[i]]=max(0,height[rank[i-1]]-1);
		if(rank[i]==1)continue;
		int j=sa[rank[i]-1];
		while(max(i,j)+height[rank[i]]<=n
				&&a[i+height[rank[i]]]==a[j+height[rank[i]]])
			height[rank[i]]++;
	}
}

char s[maxn],ss;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		cin>>ss;
		scanf("%s",s+1);
		int n=strlen(s+1);
		vector<int>vec;
		for(int i=1;i<=n;i++){
			a[i]=s[i]-'a';
			if(s[i]==ss)
				vec.push_back(i);
		}
		build_sa(n);
		long long ans=0;
		for(int i=1;i<=n;i++){
			int x=height[i];
			int len=n-sa[i]+1;
			int p=lower_bound(vec.begin(),vec.end(),sa[i])-vec.begin();
			if(p==vec.size())continue;
			x=max(x,vec[p]-sa[i]);
			ans+=len-x;
		}
		static int t=0;
		printf("Case #%d: ",++t);
		cout<<ans<<endl;
	}
	return 0;
}