后缀自动机,SAM。这玩意可以解决一群字符串问题,但是它本身的原理相当复杂,因此理解这玩意比较困难(10 级考点)。以下基本没有证明。
定义
SAM 可以在线性的空间和时间复杂度内表示给定字符串的所有子串。当然它肯定是自动机,所以来看看它在自动机方面的一些特点。
- SAM 是个 DAG。节点叫做状态,边叫做转移。注意,和PAM不同,每个节点并不只代表一个串。至于具体代表什么一会再说。
- 存在源点 \(S\),叫做初始状态,可以到达其他所有点。
- 每个转移标有一些字母,从一个节点出发的所有转移不同。
- 存在一个或多个终止状态。从初始状态出发到达一个终止状态,经过的转移边形成的字符串是原串的一个后缀。
- 在所有满足上述条件的自动机中,SAM 的点数最少。(好像需要 Nerode 定理,如果这一条有知道为啥的老哥评论讲一下谢谢)
具体的一些例子见oiwiki。
两个前置东西
- 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\) 的后缀。
显然。
\[\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} \]两个非空子串 \(u,w(|u|<|w|)\) 一定满足:
也很显然。
2. parent 树
当然自动机要有失配指针。SAM的失配指针同样形成一棵树,我们称其为 parent 树,树边称为后缀链接。一个节点 \(v\) 代表的 \(\text{endpos}\) 集合中最长的字符串为 \(w\),那么其在 parent 树上的父亲是对应与 \(w\) 的 \(\text{endpos}\) 不同的最长的 \(w\) 的一个后缀。以下我们记 \(w\) 为 \(\text{len}(v)\)。
构造
我们可以把原串逐个字符插入 SAM 。我们暂时不标记终止状态,在构造完成之后再标记。
一开始 SAM 只有一个状态 \(t_0\) ,为空串。然后插入字符 \(c\) 时顺序执行以下步骤:
- 令 \(last\) 为添加字符 \(c\) 前整个字符串的状态。
- 创建新状态 \(cur\) ,并将 \(\text{len}(cur)\) 赋值为 \(\text{len}(last)+1\)。
- 从状态 \(last\) 开始在 parent 树上往上跳。如果这个点没有到字符 \(c\) 的转移,则添加一个到状态 \(cur\) 的转移,否则停止,记停止状态为 \(p\),从 \(p\) 通过字符 \(c\) 转移到的状态为 \(q\)。
- 如果没有找到 \(p\) ,那么直接将 \(\text{fa}(cur)\) 赋值 \(t_0\)。
- 如果 \(\text{len}(p)+1=\text{len}(q)\) ,那么 \(\text{fa}(cur)\) 赋值 \(q\) 。
- 否则,创建新状态 \(tmp\) ,将 \(q\) 除了 \(len\) 以外的所有信息给 \(tmp\) ,且 \(\text{len}(tmp)=\text{len}(p)+1\)。赋值后使得 \(\text{fa}(cur)=\text{fa}(q)=tmp\)。最后从状态 \(p\) 往上跳,只要存在通过 \(p\) 到 \(q\) 的转移,就把它变成到状态 \(tmp\) 的转移。
- 完成以上过程后将 \(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|\)。
考虑算法每个部分,只有三个部分有点问题:
- 上面第 3 步在 parent 树上跳后缀链接。
- 状态 \(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