【后缀自动机】找相同字符

字符串

传送门：LOJ2064

思路：

  • 将A串建成后辍缀自动机，用B串在自动机上跑；
  • 匹配的贡献是$(lcp-stt_{fa_x})\times sz_x$，同时更新前面的值；
  • 由于$lcp>stt_{fa_x}$，对前面的更新只要标记一下再往回传即可。

注意：

  • 标记（贡献）不要算重。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 800000
LL p,np,q,nq,cnt,fa[N],stt[N],c[N][30],f[N],g[N],sum[N],qq[N],sz[N];
char s[N];
void extend(LL w){
	p=np; stt[np=++cnt]=stt[p]+1; sz[np]++;
	for (;p && !c[p][w];p=fa[p]) c[p][w]=np;
	if (!p) fa[np]=1;
	else{
		if (stt[q=c[p][w]]==stt[p]+1) fa[np]=q;
		else{
			stt[nq=++cnt]=stt[p]+1;
			memcpy(c[nq],c[q],sizeof c[q]);
			fa[nq]=fa[q]; fa[q]=fa[np]=nq;
			for (;p && c[p][w]==q;p=fa[p]) c[p][w]=nq;
		}
	}
}
void solve(char s[]){
	LL xb=1,len=strlen(s+1),ans=0,tmp=0;
	for (int i=1;i<=cnt;i++) sum[stt[i]]++;
	for (int i=1;i<=cnt;i++) sum[i]+=sum[i-1];
	for (int i=1;i<=cnt;i++) qq[sum[stt[i]]--]=i;
	for (int i=cnt;i>=1;i--) sz[fa[qq[i]]]+=sz[qq[i]];
	for (int i=1;i<=len;i++){
		LL w=s[i]-'a'+1;
		while (xb && !c[xb][w]) xb=fa[xb];
		if (!xb){xb=1; tmp=0;}
		else{tmp=min(tmp,stt[xb])+1; xb=c[xb][w]; ans+=(tmp-stt[fa[xb]])*sz[xb]; f[xb]++;}
	}
	for (int i=cnt;i>=1;i--) g[fa[qq[i]]]+=f[qq[i]]+g[qq[i]];
	for (int i=1;i<=cnt;i++) ans+=g[i]*(stt[i]-stt[fa[i]])*sz[i];
	printf("%lld\n",ans);
}
int main(){                        
	scanf("%s",s+1);
	LL len=strlen(s+1); np=++cnt;
	for (LL i=1;i<=len;i++) extend(s[i]-'a'+1);
	scanf("%s",s+1); solve(s);
	
	return 0;
}