【题解】后缀自动机(SAM)选做(22.8.11)

2022/8/11 23:30:08

本文主要是介绍【题解】后缀自动机(SAM)选做(22.8.11),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

做完这些我才感觉我的后缀自动机入门了之前写的东西就是一坨屎
对于后缀自动机的学习,我总结了以下三句话:
千万不要死磕模板!!!
千万不要死磕模板!!!
千万不要死磕模板!!!
谁死磕模板谁&#*%#(@#
这次就主要是我对于后缀自动机的理解,只是纯纯的自动机,不包含如何构造,因为那东西实在不行就背背板子,下面开始正文。

重复旋律 5

题目描述:

求本质不同的子串个数。

题目分析:

我们知道后缀自动机的几个性质:

  1. 后缀自动机的每个状态代表 \(\text{endpos}\) 相同的子串的集合,后缀自动机可以接受一个字符串的所有子串
  2. 后缀自动机的每个状态包含的字符串不交,这些字符串且满足长度递减且连续,即其长度为 \(k,k-1,k-2,\cdots\),且均为最长的子串的后缀。
  3. 后缀自动机的 \(fail\) 指针指向当前状态内的最长子串的最长的不在当前状态的后缀,即 \(\text{endpos}\) 与当前状态不同。设这个后缀的长度为 \(len\),也就是说长度为 \(len+1\) 的后缀在这个状态里面。

由以上的性质我们可以发现:我们如果能够知道每一个状态其代表的字符串的个数,那么求和之后就是全部的本质不同的子串个数。
我们也可以得到:设状态 \(x\) 的最长子串的长度为 \(len[x]\),那么 \(x\) 内子串的长度为:\([len[fail[x]]+1,len[x]]\),也就是状态 \(x\) 内的子串数量为:\(len[x] - len[fail[x]]\)

代码详解:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 1e6+5;
const int MAXM = 2 * MAXLEN;  //状态数是 2 * len - 1 
const int MAXN = 2 * MAXLEN;
const int ALP = 26; 
struct state{ //SAM 的结构体 
	int len,link;
	int nxt[27];
}st[MAXLEN * 2];
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[MAXM];
int sz,last,ans,tot[MAXN],head[MAXN],cnt;
char s[MAXN];
void sam_init(){  //SAM 的初始化 
	st[0].len = 0;st[0].link = 0;sz=1;last=1;
}
void sam_extend(int c){  //SAM 的构造,以 1 号节点为源点 
	int p = last;
	int cur = last = ++sz;
	tot[cur] = 1;
	st[cur].len = st[p].len + 1;
	while(p && !st[p].nxt[c]){
		st[p].nxt[c] = cur;
		p = st[p].link;
	}
	if(!p)	st[cur].link = 1;
	else{
		int q = st[p].nxt[c];
		if(st[p].len + 1==st[q].len)	st[cur].link = q;
		else{
			int clone = ++sz;
			st[clone] = st[q];st[clone].len = st[p].len+1;
			while(p && st[p].nxt[c] == q){
				st[p].nxt[c] = clone;
				p = st[p].link;
			}
			st[q].link = st[cur].link = clone;
		}
	}
}
signed main(){
	sam_init(); 
	int n;
	scanf("%lld",&n);
	scanf("%s",s+1);
	for(int i=1; i<=n; i++)	sam_extend(s[i] - 'a');  //构造自动机
	int ans = 0;
	for(int i=1; i<=sz; i++)	ans = ans + st[i].len - (st[st[i].link].len + 1) + 1;  //推出的式子
	printf("%lld\n",ans);
	return 0;
}

重复旋律 6

题目描述:

求出长度为 \(1,2,3,\cdots,n\) 的子串中,出现次数最多的串的出现次数。

题目分析:

我们知道后缀自动机有以下的性质:

  1. 对于不同状态内的子串不交,即不存在两个状态可以接受同一个字符串
  2. 对于不同状态的 \(\text{endpos}\) 集合,只存在包含或没有交集的关系

我们会发现:如果我们可以知道 \(\text{endpos}\) 集合的大小,那么我们就可以知道当前状态下的子串的出现次数,因为对于不同的状态代表的子串一定不交,其的 \(\text{endpos}\) 只有包含与交集为空。
那么问题就是我们如何求解 \(\text{endpos}\) 集合的大小。
我们会发现在 \(fail\) 树中,\(i\) 出现的所有位置 \(fail[i]\) 都会出现,因为 \(fail[i]\) 代表的子串中有 \(i\) 代表的子串中的后缀,所以 \(i\) 的 \(\text{endpos}\) 集合的大小,就是所有它在 \(fail\) 树上的儿子的 \(\text{endpos}\) 集合的大小之和。
但是这样会有一个特例:当状态 \(i\) 不是分裂出去的点,也就是 \(i\) 是正常的原串的前缀的话,其 \(\text{endpos}\) 集合会加一。
因为在这个位置出现的只能是这个前缀或者是这个前缀的后缀,而显然它的儿子中不可能是它的后缀,相反它可能是他的儿子的后缀。
总结一下步骤:

  • 求解 \(\text{endpos}\) 集合大小
  • 使用 \(\text{endpos}\) 集合大小获取每个状态的对应的字符串的出现次数

代码详解:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 1e6+5;
const int MAXM = 2 * MAXLEN;  //状态数是 2 * len - 1 
const int MAXN = 2 * MAXLEN;
const int ALP = 26; 
struct state{ //SAM 的结构体 
	int len,link;
	int nxt[27];
}st[MAXLEN * 2];
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[MAXM];
int sz,last,ans,endpos[MAXN],tot[MAXN],head[MAXN],cnt,res[MAXN];
char s[MAXN];
bool flag[MAXN]; 
void sam_init(){  //SAM 的初始化 
	st[0].len = 0;st[0].link = 0;sz=1;last=1;
}
void sam_extend(int c){  //SAM 的构造,以 1 号节点为源点 
	int p = last;
	int cur = last = ++sz;flag[sz] = true;
	tot[cur] = 1;
	st[cur].len = st[p].len + 1;
	while(p && !st[p].nxt[c]){
		st[p].nxt[c] = cur;
		p = st[p].link;
	}
	if(!p)	st[cur].link = 1;
	else{
		int q = st[p].nxt[c];
		if(st[p].len + 1==st[q].len)	st[cur].link = q;
		else{
			int clone = ++sz;
			st[clone] = st[q];st[clone].len = st[p].len+1;
			while(p && st[p].nxt[c] == q){
				st[p].nxt[c] = clone;
				p = st[p].link;
			}
			st[q].link = st[cur].link = clone;
		}
	}
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now){
	if(flag[now])	endpos[now] = 1;  //判断是正常的后缀
	for(int i = head[now]; i; i = e[i].nxt){
		int to = e[i].to;
		dfs(to);
		endpos[now] += endpos[to]; 
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	sam_init(); 
	scanf("%s",s+1);int n = strlen(s+1);
	for(int i=1; i<=n; i++)	
		sam_extend(s[i] - 'a');
	for(int i=2; i<=sz; i++)	add_edge(st[i].link,i);   //建 fail 树
	dfs(1);
	for(int i=1; i<=sz; i++)	res[st[i].len] = max(res[st[i].len],endpos[i]);   //这里很妙,因为对于 len 的每一个,[1,len] 这 len 的后缀肯定都出现了 
	for(int i=n-1; i>=1; i--)	res[i] = max(res[i],res[i+1]);
	for(int i=1; i<=n; i++)	printf("%lld\n",res[i]);
	return 0;
}

重复旋律 7

题目描述:

给定若干个由数字构成的串,求所有串的子串所对应的数字的和。
例如 123 的结果就是:\(1 + 2 + 3 + 12 + 23 + 123 = 164\)

题目分析:

我们知道后缀自动机有以下性质:

  1. 由字符的转移所构成的图是一个有向无环图

那么我们就可以考虑在这个有向无环图上 \(DP\) 求解。我们先考虑如果只有一个串如何解决:
显然可以得到 \(dp[i]\) 表示以 \(i\) 为终点的子串的数字和。因为后缀自动机中可以接受所有的子串,所以将所有的 \(dp\) 值求和就是答案。
转移显然就是枚举字符的转移是哪个,假设为 \(x\)

\[dp[i]\times 10 + cnt[i]\times x \to dp[nxt[i][x]] \]

其中 \(cnt[i]\) 代表到达状态 \(i\) 的路径条数,也就是以 \(i\) 为终点的子串数量(相信 \(cnt\) 数组都会求)
那么对于多个子串我们显然可以将这几个子串连起来,中间使用字符集之外的符号连接,这样我们的 \(cnt\) 和 \(dp\) 的定义就可以顺势改为不包含这个特殊符号的前提下。

代码详解:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 1e6+5;
const int MAXM = 2 * MAXLEN;  //状态数是 2 * len - 1 
const int MAXN = 2 * MAXLEN;
const int ALP = 12; 
const int MOD = 1e9+7; 
struct state{ //SAM 的结构体 
	int len,link;
	int nxt[27];
}st[MAXLEN * 2];
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[MAXM];
int sz,last,tot[MAXN],head[MAXN],cnt[MAXN],val[MAXN],num[MAXN];
char s[MAXN];
void sam_init(){  //SAM 的初始化 
	st[0].len = 0;st[0].link = 0;sz=1;last=1;
}
void sam_extend(int c){  //SAM 的构造,以 1 号节点为源点 
	int p = last;
	int cur = last = ++sz;
	tot[cur] = 1;
	st[cur].len = st[p].len + 1;
	while(p && !st[p].nxt[c]){
		st[p].nxt[c] = cur;
		p = st[p].link;
	}
	if(!p)	st[cur].link = 1;
	else{
		int q = st[p].nxt[c];
		if(st[p].len + 1==st[q].len)	st[cur].link = q;
		else{
			int clone = ++sz;
			st[clone] = st[q];st[clone].len = st[p].len+1;
			while(p && st[p].nxt[c] == q){
				st[p].nxt[c] = clone;
				p = st[p].link;
			}
			st[q].link = st[cur].link = clone;
		}
	}
}
void topo(){
	for(int i=1; i<=sz; i++){
		for(int j=0; j<=10; j++){
			if(st[i].nxt[j]) 
				cnt[st[i].nxt[j]]++;   //记录入度
		}
	} 
	queue<int> q;q.push(1); 
	num[1] = 1;
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<=10; i++){
			int to = st[now].nxt[i];
			if(to){
				if(i != 10)	val[to] = (val[to] +  (val[now] * 10)%MOD + (i * num[now])%MOD)%MOD;   //10 即字符集之外的特殊字符,不考虑这个字符
				if(i != 10)	num[to] = (num[to] + num[now])%MOD;
				cnt[to]--;
				if(cnt[to] == 0)	
					q.push(to);
			}
		}
	}
	int ans = 0;
	for(int i=1; i<=sz; i++){   //对所有的状态累计
		ans = (ans + val[i])%MOD;
	}
	printf("%lld\n",ans);
} 
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout); 
	sam_init();
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);int m = strlen(s+1);
		for(int i=1; i<=m; i++)	sam_extend(s[i] - '0');
		if(i != n)	sam_extend(10); 
	}
	topo();
	return 0;
}

重复旋律 8

题目描述:

给定 \(n\) 个字符串 \(t\) 和一个字符串 \(s\),求 \(t\) 的所有循环同构在 \(s\) 中的出现次数,出现多次便重复统计。

题目分析:

对于循环同构我们显然可以将字符串倍长,然后判断长度为原长的字符串的出现次数。
我们可以考虑对于每一个字符串 \(t\) 该如何求解:
我们考虑对每一个 \(t[i]\) 作为结束位置维护两个值:\(u\) 表示以 \(t[i]\) 为结尾的最长公共子串对应的 SAM 里的状态,\(len\) 表示以 \(t[i]\) 为结尾的最长公共子串的长度。显然如果最长公共子串的长度大于等于原长,那么就意味着以 \(t[i]\) 为结尾的这个循环同构会出现 \(|\text{endpos}(u)|\) 次。
那么就考虑知道了 \(i\) 如何求解 \(i+1\):
对于这个的求解我们显然可以类似 KMP 去求解,如果失配,也就是当前的点没有 \(t[i+1]\) 的转移,那么就跳 \(fail\),直到跳到一个点有 \(t[i+1]\) 的转移,因为这样能保证最后的部分一定可以匹配,而如果跳到最后都没有 \(t[i+1]\) 的转移,那么就意味着这个字符串没出现过。
需要注意以下的几点细节:

  1. 我们如果多次到达某一个状态,那么只计算一次贡献。例如 aaaa 显然其循环同构只有 aaaa 而非四个 aaaa
  2. 我们可能在匹配的时候出现 \(len\) 大于原长的情况,那么此时我们现在的这个循环同构就是我们找到的状态的后缀,那么我们可能可以通过跳 \(fail\),使得 \(len\) 在大于等于原长的情况下尽可能小,这样就可能导致 \(|\text{endpos}|\) 变大。

可以发现我们求解一个字符串的时间复杂度是 \(O(|t|)\) 的,因为我们最多跳 \(|t|\) 次字符转移,也就是不可能跳超过 \(|t|\) 次 \(fail\)。
那么我们就对于所有的字符串每个都跑一遍就好了。

代码详解:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 1e6+5;
const int MAXM = 2 * MAXLEN;  //状态数是 2 * len - 1 
const int MAXN = 2 * MAXLEN;
const int ALP = 26; 
struct state{ //SAM 的结构体 
	int len,link;
	int nxt[27];
}st[MAXLEN * 2];
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[MAXM];
int sz,last,ans,endpos[MAXN],tot[MAXN],head[MAXN],cnt,res[MAXN];
char s[MAXN],t[MAXN];
bool flag[MAXN],vis[MAXN]; 
void sam_init(){  //SAM 的初始化 
	st[0].len = 0;st[0].link = 0;sz=1;last=1;
}
void sam_extend(int c){  //SAM 的构造,以 1 号节点为源点 
	int p = last;
	int cur = last = ++sz;flag[sz] = true;
	tot[cur] = 1;
	st[cur].len = st[p].len + 1;
	while(p && !st[p].nxt[c]){
		st[p].nxt[c] = cur;
		p = st[p].link;
	}
	if(!p)	st[cur].link = 1;
	else{
		int q = st[p].nxt[c];
		if(st[p].len + 1==st[q].len)	st[cur].link = q;
		else{
			int clone = ++sz;
			st[clone] = st[q];st[clone].len = st[p].len+1;
			while(p && st[p].nxt[c] == q){
				st[p].nxt[c] = clone;
				p = st[p].link;
			}
			st[q].link = st[cur].link = clone;
		}
	}
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now){
	if(flag[now])	endpos[now] = 1;
	for(int i = head[now]; i; i = e[i].nxt){
		int to = e[i].to;
		dfs(to);
		endpos[now] += endpos[to]; 
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	sam_init();
	scanf("%s",s+1);int n = strlen(s+1);
	for(int i = 1; i<=n; i++){
		sam_extend(s[i] - 'a');
	}
	for(int i=1; i<=sz; i++){   //构造 fail 树,获取 endpos
		add_edge(st[i].link,i);
	}
	dfs(1);
	int q;
	scanf("%lld",&q);
	while(q--){
		int ans = 0;
		memset(vis,false,sizeof(vis));
		scanf("%s",t+1);int m = strlen(t+1);
		for(int j=m+1; j<2*m; j++)	t[j] = t[j - m];
		int now = 1,len = 0;
		for(int i=1; i<=2*m-1; i++){
			while(!st[now].nxt[t[i] - 'a']){  //暴力跳 fail 找到有 t[i] 的转移的边
				now = st[now].link,len = st[now].len;
				if(now == 1)	break;
			}
			if(st[now].nxt[t[i]-'a'])	now = st[now].nxt[t[i] - 'a'],len++;
			else	now = 1,len = 0;  //没有转移也就是没有那么就回到最初状态
			if(len > m){  //len > |t| 的情况
				while(st[st[now].link].len >= m)
					now = st[now].link,len = st[now].len;
			}
			if(len >= m && !vis[now]){  //每个状态只被访问一次
				ans += endpos[now];
				vis[now] = true;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
} 

会发现我的板子就是直接复制的,所以其实板子并没有任何的含金量。



这篇关于【题解】后缀自动机(SAM)选做(22.8.11)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程