111qqz的小窝

老年咸鱼冲锋!

【施工中】SAM学习笔记

*在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*

怕是老年人的最后一篇算法学习笔记了

心情不好,此文无限期tj

概述

主要讲解在我学习的过程中比较难理解的地方..并不保证全面

首先,后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机,也就是DFA

SAM同时具有自动机和树的性质。

节点(状态)

SAM中的节点,也叫状态。

明确一个说法:“一个节点所表示的字符串”。

由于一个字符串的子串一定是某个后缀的前缀。

因此一个字符串的子串一定可以在SAM上运行。

因此“一个节点Q所表示的字符串”的含义是说,从初始状态开始,运行该字符串后,到达的状态是Q.

一个节点所表示的字符串长度属于范围[MIN,MAX],并且区间中每个长度的字符串都出现一次

能表示的字符串长度范围有最大值很好理解,有最小值是因为:长度越小的字符串出现的位置越多,因此当长度小于MIN之后,其出现的位置增加。

由于后文见到,SAM中状态是终点位置集合的等价类,因此一个节点所表示的字符串长度存在一个最小值。

后文还问见到,一个节点的MIN恰好是其父亲节点的MAX+1

终点集合 (endpos / Right)

终点集合一般国内的资料叫right集合,国外好像更常见的叫法是endpos集合。

其实就是对于一个子串a,其在母串S中出现的位置的右端点的集合。

那么这个right集合有什么作用呢?

考虑naive的做法,一个串S有O(n^2)的后缀,凉凉

那么我们发现,对于right集合相同的两个子串,代表其子串的状态(意思是说,从初始状态到该状态所表示的字符串)是可以合并的。

为什么?因为这两个子串的所有出现位置的右端点相同,那么在其后面添加若干字符得到的后缀也一定完全相同。

那么我们可以根据right集合,将字符串的子串分成若干个等价类

对于一个等价类,我们在SAM中用一个状态表示就行了。

接下来考虑right集合的性质。

right[v]表示状态v所表示的子串出现的次数。

 

后缀链/parent树

对于不为初始状态的所有状态,一个状态对应着一个等价类,令w作为其中最长的子串,其余的子串都是w的后缀。

w的所有后缀中,一部分在w所在的等价类中,另外一部分位于其他的等价类中。于是定义后缀链link(v)连接w所有后缀中位于其他等价类并且长度最长的那个后缀所在的等价类。

 

那么根据后缀链的定义,以及后缀的长度是连续的(“后缀的长度是连续的”的含义是说,一个长度为k的字符串,一定有长度为k,为k-1,一直到长度为1的后缀)

因此一个节点的MIN恰好是其父亲节点的MAX+1  (MIN,MAX分别表示一个节点所能表示的字符串的最小值和最大值)

 

复杂度

后缀自动机·张的知乎专栏_震惊!SAM复杂度竟如此显然!

%%%qc大爷

 

构造方法

这个算法是在线的,每次在构造好的自动机的基础上增加一个字符。

对于每个状态,需要保存lenlink以及转移状态信息。

初始条件下,自动机只包含一个起始状态t0len=0并且link指向-1。所有算法要做的就是给后缀自动机增加一个新的字符c。

  • 我们用last来表示当前需要增加一个字符的状态,初始情况下last=0,之后每次增加字符后都会修改。
  • 创建一个新的状态cur,要求len(cur)=len(last)+1link先留着。
  • 接下来进行这样的循环:从last状态开始,如果不存在字符c的转移,那么增加一个到达cur的字符c的转移,然后沿着后缀链继续检查——如果不存在字符串c的转移,那么增加一个转移;如果字符串c的转移已经存在,那么停止循环,将停止时检查的状态记为p。这个时候,会出现两种情况:
    • 如果一直没有遇到存在转移的状态,那么最终我们会到达伪状态-1,只需要让link(cur)=0后退出。
    • 如果遇到存在字符c转移的状态,另q为转移到的状态,那么又有了两种情况:
      • 如果len(p)+1=len(q),只需要令link(cur)=q后退出。
      • 否则,创建一个新的状态clone,将q的转移也拷贝给clone,令len(clone)=len(p)+1。然后,将状态cur和状态q的后缀链指向clone。最后需要完成的事情就是,遍历p的后缀链上的状态,如果存在指向状态q的字符c转移,那么将这个转移重定向到clone(如果不存在,遍历停止)
  • 在任何一种情况下,最后都需要将last设置为cur。

根据后缀链的定义,last开始的后缀链上的状态就是自动机的所有终止状态。

 

 

我的模板

出于太懒的原因,没有封装

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

 

 

 

 

 

 

 

 

SA&&SAM论文

 SAM学习指南

 

fanhq666_后缀自动机与线性构造后缀树

后缀自动机(SAM)

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz