P3181 [HAOI2016]找相同字符【后缀数组】

传送门
用后缀数组写这个题太反智了，因为是 (O(n^2)) 的统计答案，所以要用单调栈来做优化，比广义后缀自动机麻烦太多了，这个题就是广义后缀自动机的板子题。
由此可见后缀数组还是处理单字符串或者处理多字符串的长度问题好用一些，这种处理多字符串的方案统计问题就算了

后缀数组代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+10;
char s[N],t[N];
int n,sa[N*2],rk[N*2],tp[N*2],ht[N],m,c[N],id[N];
int sta[N],top,num[N];

void getsa(){
	m='z';
	for(int i=1;i<=n;i++) c[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i;
	for(int w=1,p=0;p<n;w<<=1,m=p){
		p=0;
		for(int i=n-w+1;i<=n;i++) tp[++p]=i;
		for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[rk[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[rk[tp[i]]]--]=tp[i];
		swap(tp,rk);
		rk[sa[1]]=p=1;
		for(int i=2;i<=n;i++)
			rk[sa[i]]=(tp[sa[i]]>tp[sa[i-1]]||tp[sa[i]+w]>tp[sa[i-1]+w])?++p:p;
	}
	int k=0;
	for(int i=1;i<=n;i++){
		if(rk[i]==1) continue;
		if(k) k--;
		int j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]) k++;
		ht[rk[i]]=k;
	}
	LL ans=0,sum=0;
	for(int color=1;color<=2;color++){
		top=sum=0;
		for(int i=1;i<=n;i++){
			if(ht[i]==0) {top=sum=0;continue;}
			int cnt=0;
			if(id[sa[i-1]]!=color) cnt++,sum+=ht[i];
			while(top&&ht[i]<=sta[top]) {
				cnt+=num[top];
				sum-=1ll*num[top]*(sta[top]-ht[i]);
				top--;
			}
			sta[++top]=ht[i],num[top]=cnt;
			if(id[sa[i]]==color) ans+=sum;
		}
	}
	printf("%lld
",ans);
}

int main(){
	scanf("%s%s",s+1,t+1);
	strcat(s+1,"#");
	strcat(s+1,t+1);
	n=strlen(s+1);
	for(int i=1,p=1;i<=n;i++){
		if(s[i]=='#') ++p;
		else id[i]=p;
	}
	getsa();
	return 0;
}

后缀自动机代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+10;
char s[N];
int n;

struct SuffixAutomataPro{
	int tot=1,len[N*2],fa[N*2],ch[N*2][26],A[N*2],B[N*2],*ep,c[N],a[N*2];
	int newnode(int x){fa[++tot]=fa[x];len[tot]=len[x];memcpy(ch[tot],ch[x],sizeof(ch[tot]));return tot;}
	int extend(int p,int c){
		int q=ch[p][c],nq=newnode(q);
		len[nq]=len[p]+1;fa[q]=nq;
		for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		return nq;
	}
	int append(int p,int c){
		if(ch[p][c]) if(len[ch[p][c]]==len[p]+1) return ch[p][c];else return extend(p,c);
		int np=newnode(0);len[np]=len[p]+1;
		for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
		if(!p) fa[np]=1;
		else if(len[ch[p][c]]==len[p]+1) fa[np]=ch[p][c];
		else fa[np]=extend(p,c);
		return np;
	}
	void insert(int *epos){
		ep=epos;
		for(int i=1,p=1;i<=n;i++) p=append(p,s[i]-'a'),ep[p]=1;
	}
	void solve(){
		for(int i=1;i<=tot;i++) c[len[i]]++;
		for(int i=1;i<=n;i++) c[i]+=c[i-1];
		for(int i=tot;i>=1;i--) a[c[len[i]]--]=i;
		for(int i=tot;i>=2;i--) A[fa[a[i]]]+=A[a[i]],B[fa[a[i]]]+=B[a[i]];
		LL ans=0;
		for(int i=2;i<=tot;i++) ans+=1ll*(len[i]-len[fa[i]])*A[i]*B[i];
		printf("%lld
",ans);
	}
}sam;

int main(){
	scanf("%s",s+1);n=strlen(s+1);
	sam.insert(sam.A);
	scanf("%s",s+1);n=strlen(s+1);
	sam.insert(sam.B);
	sam.solve();
	return 0;
}