首页 > 其他分享 >后缀自动机,SAM

后缀自动机,SAM

时间:2022-12-19 17:47:58浏览次数:35  
标签:状态 SAM 后缀 text len endpos 自动机 转移

后缀自动机,SAM。这玩意可以解决一群字符串问题,但是它本身的原理相当复杂,因此理解这玩意比较困难(10 级考点)。以下基本没有证明。

定义

SAM 可以在线性的空间和时间复杂度内表示给定字符串的所有子串。当然它肯定是自动机,所以来看看它在自动机方面的一些特点。

  1. SAM 是个 DAG。节点叫做状态,边叫做转移。注意,和PAM不同,每个节点并不只代表一个串。至于具体代表什么一会再说。
  2. 存在源点 \(S\),叫做初始状态,可以到达其他所有点。
  3. 每个转移标有一些字母,从一个节点出发的所有转移不同。
  4. 存在一个或多个终止状态。从初始状态出发到达一个终止状态,经过的转移边形成的字符串是原串的一个后缀。
  5. 在所有满足上述条件的自动机中,SAM 的点数最少。(好像需要 Nerode 定理,如果这一条有知道为啥的老哥评论讲一下谢谢)

具体的一些例子见oiwiki。

两个前置东西

  1. endpos

对于串 \(s\) 的一个非空子串 \(t\) ,记 \(\text{endpos}(t)\) 为在字符串 \(s\) 中 \(t\) 的所有结束位置。举个例子, \(abcbc\) 中 \(\text{endpos}(t)=\{3,5\}\)。

显然,两个字符串的 \(\text{endpos}\) 可能相同,而且假设 \(s[l\dots r]\) 是一个集合中最长的串,那么这个集合中的所有串是 \(s[l\dots r],s[l+1\dots r],\dots,s[l+x\dots r](x\in[0,r-l+1])\)。也就是往后的连续若干个后缀。SAM 的每个节点正是代表一个 \(\text{endpos}\) 集合中的所有串。我们可以得到一些结论:

字符串 \(s\) 的两个非空子串 \(u,w(|u|<|w|)\) 的 \(\text{endpos}\) 相同,当且仅当 \(u\) 在 \(s\) 中的每次出现都是 \(w\) 的后缀。

显然。

两个非空子串 \(u,w(|u|<|w|)\) 一定满足:

\[\begin{cases} \text{endpos}(w)\subseteq \text{endpos}(u) & u\ \text{is a suffix of w}\\ \text{endpos}(w)\cap \text{endpos}(u)=\varnothing & \text{otherwise} \end{cases} \]

也很显然。
2. parent 树

当然自动机要有失配指针。SAM的失配指针同样形成一棵树,我们称其为 parent 树,树边称为后缀链接。一个节点 \(v\) 代表的 \(\text{endpos}\) 集合中最长的字符串为 \(w\),那么其在 parent 树上的父亲是对应与 \(w\) 的 \(\text{endpos}\) 不同的最长的 \(w\) 的一个后缀。以下我们记 \(w\) 为 \(\text{len}(v)\)。

构造

我们可以把原串逐个字符插入 SAM 。我们暂时不标记终止状态,在构造完成之后再标记。

一开始 SAM 只有一个状态 \(t_0\) ,为空串。然后插入字符 \(c\) 时顺序执行以下步骤:

  1. 令 \(last\) 为添加字符 \(c\) 前整个字符串的状态。
  2. 创建新状态 \(cur\) ,并将 \(\text{len}(cur)\) 赋值为 \(\text{len}(last)+1\)。
  3. 从状态 \(last\) 开始在 parent 树上往上跳。如果这个点没有到字符 \(c\) 的转移,则添加一个到状态 \(cur\) 的转移,否则停止,记停止状态为 \(p\),从 \(p\) 通过字符 \(c\) 转移到的状态为 \(q\)。
  4. 如果没有找到 \(p\) ,那么直接将 \(\text{fa}(cur)\) 赋值 \(t_0\)。
  5. 如果 \(\text{len}(p)+1=\text{len}(q)\) ,那么 \(\text{fa}(cur)\) 赋值 \(q\) 。
  6. 否则,创建新状态 \(tmp\) ,将 \(q\) 除了 \(len\) 以外的所有信息给 \(tmp\) ,且 \(\text{len}(tmp)=\text{len}(p)+1\)。赋值后使得 \(\text{fa}(cur)=\text{fa}(q)=tmp\)。最后从状态 \(p\) 往上跳,只要存在通过 \(p\) 到 \(q\) 的转移,就把它变成到状态 \(tmp\) 的转移。
  7. 完成以上过程后将 \(last\) 的值改为 \(cur\)。

如何标记终止状态?整个串 \(s\) 在 parent 树上的所有祖先都是终止状态。

正确性证明

假设加入字符前的 SAM 是正确的,只需要证明操作后的 SAM 仍然正确。

转移边 \((p,q)\) 有两种情况:\(\text{len}(q)=\text{len}(p)+1\),或者\(\text{len}(q)>\text{len}(p)+1\)。对于第一种情况,称其为连续的,反之为不连续的。显然,连续的转移边再也不会动了,而不连续的可能会在中间插进来某些转移。

我们只需要对 4-6 三步对应的三种情况进行讨论。第一种情况的正确性是显然的。二和三的不是那么一眼。

我们尝试向自动机内添加一个已经存在的字符串 \(x+c\)(\(x\) 为插入前串的一个后缀)。既然原来的 SAM 正确,那么不必添加新转移。现在考虑 \(cur\) 的 \(\text{fa}\) 连到哪里。我们连到一个状态,满足最长的字符串是 \(x+c\),也就是 \(\text{len}=\text{len}(p)+1\)。那么第二种情况也很显然了。

否则,转移不连续。我们将状态 \(q\) 拆开成两个子状态,一个长度是 \(\text{len}(p)+1\) ,另一个是原来的长度。这个操作就相当于把原来 \(q\) 状态的子树都接在复制后的状态上。

最后是重定向转移边的问题。我们也只需要修改相当于所有字符串 \(w+c\) (\(w\) 是 \(p\) 的最长字符串)就行了。

复杂度证明

两种实现,一是字符集较大,可以开个 map,时间复杂度多个 \(\log|\Sigma|\)。二是字符集小,可以直接开数组,空间复杂度多个 \(|\Sigma|\)。

考虑算法每个部分,只有三个部分有点问题:

  1. 上面第 3 步在 parent 树上跳后缀链接。
  2. 状态 \(q\) 被复制到新状态时复制转移的过程。

这两个本质相同,都是增加转移。而由于 SAM 的转移数是线性的,所以这块的复杂度是线性的。
3. 重定向指向 \(q\) 的转移。

这一部分不会,留坑。

代码

void ins(char ch){
    int p=last;last=++cnt;
    len[last]=len[p]+1;
    while(p&&!trie[p][ch])trie[p][ch]=cnt,p=fa[p];
    if(!p){
        fa[last]=1;return;
    }
    int q=trie[p][ch];
    if(len[p]+1==len[q]){
        fa[last]=q;return;
    }
    len[++cnt]=len[p]+1;
    for(int j=0;j<26;j++)trie[cnt][j]=trie[q][j];
    fa[cnt]=fa[q];fa[q]=cnt;fa[last]=cnt;
    while(trie[p][ch]==q)trie[p][ch]=cnt,p=fa[p];
}

初始化 \(cnt=last=1\)。

一些性质

状态数

SAM 的状态数不超过 \(2n-1\)。一开始自动机有一个状态,第一次和第二次中只会创建一个状态,之后每次两个。上界的构造:\(\texttt{abbbb\dots b}\)。

转移数

SAM 的转移边数不超过 \(3n-4\)。

分两部分,连续的和不连续的。连续的显然构成一棵树,那么上界 \(2n-2\)。

考虑不连续的转移边 \((p,q)\) ,取字符串 \(u+c+w\) ,\(u\) 为初始状态到 \(p\) 的最长路, \(c\) 为转移边,\(w\) 为 \(q\) 到任意终止状态的最长路。那么 \(u+c+w\) 显然是原串的一个后缀。又有原串一定不是 \(u+c+w\) (原串最长路全是连续转移),那么最多 \(n-1\) 条。

此时我们有上界 \(3n-3\) 。然而最大状态数对应的 \(\texttt{abbb\dots b}\) 显然不是 \(3n-3\) ,于是上界为 \(3n-4\)。一个构造是 \(\texttt{abbb\dots bc}\)。

parent 树的一些性质

称每个前缀对应的节点为终点节点。那么有如下性质:

每个节点的 \(\text{endpos}\) 集合为其子树内所有终点节点。

同时对于每个节点的最长字符串,有:

若节点 \(A\) 是 \(B\) 的祖先,则 \(A\) 对应的字符串是 \(B\) 的后缀。

这也决定了字符串的后缀树就是反串的 parent 树。

应用等我做点题再说,可能短期内不会补。

标签:状态,SAM,后缀,text,len,endpos,自动机,转移
From: https://www.cnblogs.com/gtm1514/p/16992678.html

相关文章

  • 后缀自动机
    \(\text{SAM}\)大部分是贺OI-Wiki的。目录\(\text{SAM}\)性质概念\(\text{endpos}\)-子串在母串中的结束位置\(\text{link}\)-转移结束位置的后缀链接总结构造流程......
  • KMP 自动机
    相当于\(\pi\)函数(KMP中的next数组)的扩展。\(\delta(i,c)\)表示在KMP匹配过程中当模式串指针在\(i\),接受字符\(c\)后模式串指针所处的位置。则KMP过程中模......
  • 如何申请@MSN.Com后缀的邮箱?
    最近辞职在家无事,想申请个@MSN.Com后缀的信箱,在网上搜索了一下,原来只要从下面的地址进入注册即可!注册抵制:​​https://accountservices.passport.net/reg.srf?ns=msn.......
  • Ubuntu安装配置 Samba与 Windows 共享文件
    前言我们经常会遇到一边使用linux系统时候一边使用windows,这个时候会产生很多需要传输的文件,当然我们可以使用sshscp进行传输,或者使用FileZilla、Winscp等工具,但是这些还......
  • 空间不足了?用linux搭建samba家庭共享盘
    目录背景--空间不够,文件太散乱环境搭建硬盘开机自动挂载samba安装配置参考背景--空间不够,文件太散乱最近在使用各种设备的时候,总是觉得存储空间告急。总觉得现在不太喜......
  • 回文自动机,PAM
    回文自动机。或者叫回文树。这坑我放了一百年没填了。结构回文自动机的每个节点都代表一个回文子串。它有两个起始状态:奇根和偶根。它们是奇回文串和偶回文串的起点,不代......
  • 【openEuler系列】部署文件共享服务Samba
    个人名片:对人间的热爱与歌颂,可抵岁月冗长......
  • Go语言获取路径的文件名、后缀
    packagemainimport( "fmt" "path" "path/filepath")funcmain(){ filePath:="D:/DDPS/log/log.txt" paths,fileName:=filepath.Split(filePath) fm......
  • cookie中的SameSite属性
    我们的网页为什么能被iframe嵌入:1把网关加入应用程序的白名单,Content-Security-Policy是所谓的白名单在http协议上的体现2跨域cookie,发现应用程序的cookie压根没有设置......
  • 【学习笔记】UKK线性求后缀树
    (话说是不是可以直接SAM线性构造啊QAQ)构造过程直观图入门......