P6139 【模板】广义后缀自动机（广义 SAM）

本文主要是介绍P6139 【模板】广义后缀自动机（广义 SAM），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

研究了下概念，就学会了基于字典树的广义SAM构造方法。

北大带哥提出的别的高效构造完全不会了...

SAM是基于字符串的，GSAM就是把lst换成字典树的上一个节点就行了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+100;
int ch[maxn][26];
int ed[maxn];//每个字典树节点在GSAM里的节点编号，记得初始化ed[0]=1 
int tol;
int len[maxn],link[maxn],nxt[maxn][26];
int sz[maxn],tot=1,lst=1;
void insert (string s) {
	int u=0;
	for (char i:s) {
		if (!ch[u][i-'a']) ch[u][i-'a']=++tol;
		u=ch[u][i-'a'];
	}
}
int sam_extend (char c,int lst) {
	int cur=++tot;
	len[cur]=len[lst]+1;
	sz[cur]=1;
	int p=lst;
	while (p&&!nxt[p][c-'a']) {
		nxt[p][c-'a']=cur;
		p=link[p];
	}
	if (!p) {
		link[cur]=1;
	}
	else {
		int q=nxt[p][c-'a'];
		if (len[p]+1==len[q]) {
			link[cur]=q;
		}
		else {
			int clone=++tot;
			len[clone]=len[p]+1;
			for (int i=0;i<26;i++) {
				nxt[clone][i]=nxt[q][i];
			}
			link[clone]=link[q];
			while (p&&nxt[p][c-'a']==q) {
				nxt[p][c-'a']=clone;
				p=link[p];
			}
			link[q]=link[cur]=clone;
		}
	}
	sz[cur]=1;
	return cur;
}
void GSA (int u,int f,char lc) {
	if (u) {
		ed[u]=sam_extend(lc,ed[f]);
	} 
	for (int i=0;i<26;i++) {
		if (ch[u][i]) {
			GSA(ch[u][i],u,i+'a');
		}
	}
}
int n;
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		string s;
		cin>>s;
		insert(s);
	}
	ed[0]=1;
	GSA(0,-1,'a');
	long long ans=0;
	for (int i=2;i<=tot;i++) {
		ans+=len[i]-len[link[i]];
	}
	printf("%lld\n",ans);
	
}

这篇关于P6139 【模板】广义后缀自动机（广义 SAM）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！