浅谈后缀自动机SAM

一下是蒟蒻的个人想法，并不很严谨，仅供参考，如有缺误，敬请提出

参考资料：

陈立杰原版课件

 litble

某大神

 某大神

其实课件讲得最详实了

有限状态自动机##

我们要学后缀自动机，我们先来了解一下自动机到底是什么。【虽说以前也学过AC自动机，只是当一个名字罢了】

有限自动机的功能是识别字符串，作用各不相同

如果自动机A能识别串s，那么A(s) = true

自动机有一个初始状态，从初始状态出发能到达多个状态。到达终止状态表示字符串识别

后缀自动机SAM##

我们略去建机原理的分析和建机过程，具体原理建议看陈立杰神牛的课件，建机过程为了简化可以看litble的

其实是我弱写不出来QAQ

一些性质：

①后缀自动机能识别对应串的所有后缀，且状态数最少【最简状态】

②从初始状态出发，每一种走法唯一对应一种子串

【也就是说一个节点往后有几种走法，往后就有几种子串】

③一个状态代表一个子串集合，该集合中的子串有着相同的右端点，且长度连续

④一个状态的pre指针指向的状态与该状态也有着相同的右端点，且长度最大值 = 该状态最小长度 - 1

由此可见pre是当前串的后缀

⑤一个状态表示子串的最大长度Max(u) = step[u]，最小长度Min(u) = step[pre[u]] + 1【由④得】

⑥如果不同位置的相同子串需重复计算，则一个点表示子串的数量 = 其parent树中的叶子个数

⑦只有叶子节点表示的子串是不重复的

⑧后缀自动机是拓扑图，pre指针形成一棵树

⑨插入时第一个建的点都是主链上的点

⑩求点的拓扑序可以用step进行基数排序

一些作用：【大多与子串相关】

①求第K小子串

②求LCP【最长公共子串】

③求子串出现次数，最大次数等

④求某个位置为结尾最大匹配长度

⑤求不同子串数

还有很多。。。。。

蒟蒻见过的差不多这些

贴个模板

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)

using namespace std;

const int maxn = 2000005,maxm = 100005,INF = 1000000000;

inline int RD(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int ch[maxn][26],pre[maxn],step[maxn],n,cnt,last;

int b[maxn],sz[maxn],a[maxn];

LL ans = 0;

char s[maxn];

void ins(int u){

	int p = last,np = ++cnt;

	last = np; step[np] = step[p] + 1;

	while (p && !ch[p][u]) ch[p][u] = np,p = pre[p];

	if (!p) pre[np] = 1;

	else {

		int q = ch[p][u];

		if (step[q] == step[p] + 1) pre[np] = q;

		else {

			int nq = ++cnt; step[nq] = step[p] + 1;

			for (int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];

			pre[nq] = pre[q]; pre[q] = pre[np] = nq;

			while (ch[p][u] == q) ch[p][u] = nq,p = pre[p];

		}

	}

	sz[np] = 1;

}

void solve(){

	REP(i,cnt) b[step[i]]++;

	REP(i,cnt) b[i] += b[i - 1];

	REP(i,cnt) a[b[step[i]]--] = i;

	for (int i = cnt; i; i--){

		sz[pre[a[i]]] += sz[a[i]];

		if (sz[a[i]] > 1) ans = max(ans,1ll * step[a[i]] * sz[a[i]]);

	}

}

int main(){

	scanf("%s",s + 1);

	cnt = last = 1; n = strlen(s + 1);

	for (int i = 1; i <= n; i++) ins(s[i] - 'a');

	solve();

	printf("%lld",ans);

	return 0;

}

巴特西

浅谈后缀自动机SAM

有限状态自动机##

后缀自动机SAM##

最新文章

热门文章