CF1483F - Exam

Posted on Edited on In

CF1483F - Exam

题目大意

给定 \(n\) 个不同串 \(s_i\) ，令 \(s_i\sub s_j\) 表示 \(s_i\) 是 \(s_j\) 的子串

求所有二元组 \((i,j)(i\ne j)\) 满足

\(s_i\sub s_j,\nexists k\ne i,k\ne j,s_i\sub s_k\sub s_j\)


分析

首先可以说明答案是 \(O(\sum |s_i|)\) 级别的

对于每个 \(s_j\) 考虑其枚举 \(r\) 作为 \(s_i\) 的右端点，则 \(s_i\) 只有最长的一个会贡献答案

故每个右端点最多对应一个 \(s_i\)

一般情况下，判断子串相同的问题我们需要 \(\text{SAM}\)

但是鉴于这道题实际上需要判别的子串只有 \(n\) 个，而维护匹配只需要 \(\text{AC}\) 自动机，所以不需要 \(\text{SAM}\)

那么可以在 \(\text{AC}\) 自动机上预处理每个匹配节点在 \(\text{fail}\) 树上最近的有效祖先

即对于每个右端点找到了最长的 \(s_i\)

可以对于找到的 \(s_i\) 简单去重，但是仍然存在以下多余计算

  1. \(s_i\) 所对应的 \([l,r]\) 被某一个 \(s_i'\) 对应的 \([l',r']\) 包含的情况，可以 \(O(n)\) 判断区间包含干掉

2.一个 \(s_i\) 在这个位置被计算，但是实际上在其他位置被包含

实际上，这只需要判断 \(s_i\) 每一次被出现是否都是有效的即可

可以用树状数组+ \(\text{dfs}\) 序维护 \(s_i\) 出现的次数

时间复杂度为 \(O((\sum |s_i|)\log (\sum |s_i|))\) ，空间复杂度为 \(O((\sum |s_i|)|\Sigma|)\)

似乎是Codeforces上最快的Submission?

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const int N=1e6+10,INF=1e9+10;

int n;
int fail[N],lst[N],trie[N][26],End[N],dep[N],fa[N],L[N],R[N],I[N],dfn,cnt;
struct Edge{
	int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

void dfs(int u) {
	I[L[u]=++dfn]=u;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!lst[v]) lst[v]=lst[u];
		dfs(v);
	}
	R[u]=dfn;
}

void Build() {
	static queue <int> que;
	rep(i,0,25) if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		AddEdge(fail[u],u);
		rep(i,0,25) {
			int &v=trie[u][i];
			if(!v) v=trie[fail[u]][i];
			else fail[v]=trie[fail[u]][i],que.push(v);
		}
	}
	dfs(0);
}

struct BIT{
	int s[N];
	void Add(int p,int x){ while(p<=dfn) s[p]+=x,p+=p&-p; }
	int Que(int p){
		int res=0;
		while(p) res+=s[p],p-=p&-p;
		return res;
	}
	int Que(int l,int r){ return Que(r)-Que(l-1); }
} T;

char s[N];
int A[N],B[N],C;

int main(){
	n=rd();
	rep(i,1,n) {
		scanf("%s",s+1);
		int u=0;
		for(int j=1;s[j];++j) {
			int &v=trie[u][s[j]-'a'];
			if(!v) v=++cnt,fa[v]=u,dep[v]=dep[u]+1;
			u=v;
		}
		lst[End[i]=u]=u;
	}
	Build();
	int ans=0;
	rep(i,1,n) {
		C=0;
		for(int u=End[i],mi=1e9;u;u=fa[u]) {
			T.Add(L[u],1);
			int p=lst[u==End[i]?fail[u]:u];
			int l=dep[u]-dep[p]+1;
			if(!p || mi<=l) continue; // none or being included
			mi=l;
			if(!B[p]) A[++C]=p;
			B[p]++;
		}
		rep(j,1,C) {
			ans+=T.Que(L[A[j]],R[A[j]])==B[A[j]];
			B[A[j]]=0;
		}
		for(int u=End[i];u;u=fa[u]) T.Add(L[u],-1);
	}
	printf("%d\n",ans);
}