【文文殿下】后缀自动机(Suffix Automaton,SAM)学习笔记
2024-08-26 14:44:45
前言
后缀自动机是一个强大的数据结构,能够解决很多字符串相关的(String-related)问题。
例如:他可以查询一个字符串在另一个字符串中出现的所有子串,以及查询一个字符串中本质不同的字符串的个数。
后缀自动机可以理解为一个字符串的所有子串的压缩图,对于一个长度为\(n\)的字符串,它只需要\(O(n)\)的空间,以及\(O(n)\)的时间进行在线搭建(如果我们把字符集视作常数)。如果我们把字符集视作变量\(k\),那么他的空间复杂度和时间复杂度都可以做到\(O(nlogk)\)。后缀自动机是在1983年被提出的,随后于1985年人们发现了一个线性构造的方法。
后缀自动机的定义
对于一个给定的字符串\(S\),它的后缀自动机是一个能够接受它的所有后缀的最简确定性有限状态自动机(Minimal Deterministic Finite Automaton,MDFA)。
后缀自动机的性质(形态)
后缀自动机是一张有向无环图(Oriented Acyclic Graph,OAG),每个节点被称作状态(State),每条边称作两个状态之间的转移(Transition)。
有一个状态被称作起始状态(Initial State,IS)。它是整张OAG的起点(不存在一个状态,可以转移到它,即入度为0)。
每一个转移都表示一个字符,而一条从起始状态到其他状态的路径,都表示一个字符串。
每一个状态都认为是终态(Terminal State,TS)。如果我们能从起始状态转移到终态,那么我们经过的路径所代表的字符串一定是原串的某个后缀(我们认为空串是任何串的后缀)。
后缀自动机是满足以上性质的自动机中,拥有最少状态的一个自动机。
子串性质
后缀自动机最简单和最重要的一个性质是:它包含了一个字符串中所有子串的信息。后缀自动机上的所有路径(不必从起始状态出发),组成了原串中所有的子串。
每一个状态代表了所有从起始状态到它的路径所代表的字符串的集合。
一些简单的SAM的例子
空串
字符串 "a"
字符串"aa"
字符串"ab"
字符串"aba"
字符串"abb"
字符串"abbb"
Right集合
一个状态所代表的所有的字符串的右端点的位置。根据性质,显然这个状态里面的所有字符串的出现位置的右端点都重合。
所代表的串的长度
一个状态下所代表的所有的字符串的长度,一定是一段连续的区间。
后缀链接(parent)
两个状态\(u,v\),如果\(u\)中所有字符串都是\(v\)中某个字符串的后缀,那么从\(v\)向\(u\)连一条名为后缀链接的虚拟边,这条边并不存在于MDFA中。每个节点有且仅有一条后缀链接连向其他的状态,但他可能被多个后缀链接所指向。
我们把满足上述条件的\(u,v\),称作\(u\)是\(v\)的父亲(Parent)。
显然,一个状态所代表的字符串中最短的那条,是它父亲状态所代表的最长的那条字符串的长度+1
字符串"abcbc"的SAM与后缀链接的展示
线性构造算法(参见Menci)
代码实现
void extend(int x) { // 构建
int np = ++cnt,p=last;
Right[np]=1;
mx[np]=mx[p]+1;
last=np;
while(p&&!tr[p][x]) tr[p][x]=np,p=par[p];
if(!p) par[np]=1;
else {
int q = tr[p][x];
if(mx[q]==mx[p]+1) {
par[np]=q;
}
else {
int nq = ++cnt;
mx[nq]=mx[p]+1;
memcpy(tr[nq],tr[q],sizeof tr[q]);
par[nq]=par[q];par[q]=par[np]=nq;
while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p];
}
}
return;
}
void topsort() {//求Right数组大小
for(int i = 1;i<=cnt;++i) ++c[mx[i]];
for(int i = 1;i<=n;++i) c[i]+=c[i-1];
for(int i = 1;i<=cnt;++i) id[c[mx[i]]--]=i;
for(int i = cnt;i;--i) Right[par[id[i]]]+=Right[id[i]];
return;
}
最新文章
- ReactJS实践(一)—— FrozenUI React化之Loading组件
- mvc配合jquery.validate验证失效,情况之一
- 一个比较通用的makefile
- 常用JVM配置参数
- 【HDOJ】2209 翻纸牌游戏
- Windows 服务卸载之后 重新安装提示 “指定的服务已标记为删除”
- Linux svn直接删除版本库文件
- TCP 协议
- java web实现img读取盘符下的图像
- Android学习路线(二十)运用Fragment构建动态UI
- css修改滚动条默认样式
- java数据结构(二叉树)
- angular JS中使用jquery datatable 自定义搜索按钮点击事件 和mRender的 ng-click事件
- python -使用del语句删除对象引用
- java接口中的继承
- 微服务架构及Eureka简介
- Redis (error) NOAUTH Authentication required.解决方法
- JS 实现Json查询的方法实例
- 用C++画光(三)&mdash;&mdash;色散
- 微信JS支付代码_前端调用微信支付接口