后缀自动机 SAM

重要性质

• 后缀自动机的节点数不超过 $2n-12n-1$。

以下是字符串 $aababaaababa$ 形成的图

模版讲解

$fail[i]fail[i]$

• 指向的节点可以这么描述：

• 是当前节点表示不了的、是当前节点能表示的子串集合的后缀。
• 若当前节点能表示的最短子串为 $c+Sc+S$，那么指向的节点能表示的最长子串一定为 $SS$。

• 以下是上图中的 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 树，括号代表 当前节点表示的子串集合的长度范围

特征

• 父节点能表示的最短子串的长度 $==$ 儿子节点能表示的最长子串的长度 $+1+1$
• 每个父节点只连出一条 fail 边。
• 对于一个节点，如果该节点能表示的子串长度范围为 $[l,r][l,r]$，那么每一个长度短的一定是长度长的后缀

举例

• 注意看 6 号节点。
• 它能表示的子串集合为：$aababaabab$、$abababab$、$babbab$ （能发现，每一个长度短的一定是长度长的后缀）。
• 它的 fail 边连向 7
• 7 能表示的最长子串为 $abab$

$max\mathrm{\_}len[i]max\backslash \_len[i]$

• 该节点能表示的最长子串的长度
• 该节点能表示的子串集合的长度种类数：$max\mathrm{\_}len[cur]-max\mathrm{\_}len[pre]max\backslash \_len[cur]-max\backslash \_len[pre]$

性质

• 所有节点 $rank\mathrm{\_}max\mathrm{\_}lenrank\backslash \_max\backslash \_len$ 从第一名到最后一名，或者从最后一名到第一名，既是 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 树 的拓扑序，又是 字典树 的拓扑序。
• 可以根据每个节点 $max\mathrm{\_}lenmax\backslash \_len$ 的排名，直接拓扑排序进行DP转移，无需使用队列。

$sz[i]sz[i]$

• 当前节点所能表示的子串集合 在 整个字符串 中出现的次数。
• 注意：对于任意一个节点，都不可能有：某节点既能表示出 $S+SS+S$，又能表示出 $SS$ 的情况。
• 性质1：从某一点出发，沿着字典树往下走，$szsz$ 只可能不变或递减。
• 性质2：从某一点出发，逆着fail边往下走，$szsz$ 只可能不变或递减。

它是怎么求出来的？

• 拓扑排序。按照 $rank\mathrm{\_}max\mathrm{\_}lenrank\backslash \_max\backslash \_len$ 从 $max\mathrm{\_}lenmax\backslash \_len$ 最大到最小，进行拓扑排序。
• 初始：各节点 $sz[i]=1sz[i]=1$。
• 转移：$\sum sz[u]\to sz[v]\backslash sum\; sz[u]\; \backslash rightarrow\; sz[v]$，其中 $maxlen[u]>maxlen[v]maxlen[u]>maxlen[v]$，并且 $vv$ 是 $uu$ 通过 fail 边连向的节点。
• 代码：

for(int i=tot;i>=1;i--)
{
   int cur = rnk_len[i];
   sz[ fail[cur] ] += sz[cur];
}

例题

洛谷3975 - 弦论

题目描述

• 对于一个给定的长度为 $nn$ 的字符串，求出它的第 $kk$ 小子串。
• 第一行是一个仅由小写英文字母构成的字符串 $ss$。
• 第二行为两个整数 $tt$ 和 $kk$，$tt$ 为 $00$ 则表示不同位置的相同子串算作一个，$tt$ 为 $11$ 则表示不同位置的相同子串算作多个。

解析

• 每个节点都代表一个子串的集合，这是从 DAG（字典树） 根节点到这个点所有可能走过的路径构成的字符串的集合。
• 并且在 DAG 的某个节点上，继续往下走还会走到后续的节点。
• 因此，对于 DAG 的每个节点，我们都需要统计出在 当前点和当前点的后续节点，总共有多少子串。
• 自然联想到拓扑排序。我们知道，所有节点 rank_max_len 从第一名到最后一名，或者从最后一名到第一名，既是 fail 树 的拓扑序，又是 字典树 的拓扑序。 所以，按照拓扑序进行转移即可。
• 转移：
  • 当 $t=1t=1$ 时，初始化 $dp[i]=sz[i]dp[i]=sz[i]$，转移 $dp[u]+=\sum dp[v]dp[u]\; +=\; \backslash sum\; dp[v]$，$vv$ 是字典树拓扑序靠后的。
  • 当 $t=0t=0$ 时，初始化 $dp[i]=1dp[i]=1$，转移 $dp[u]+=\sum dp[v]dp[u]\; +=\; \backslash sum\; dp[v]$，$vv$ 是字典树拓扑序靠后的。
• 最后 DFS 遍历输出即可。

牛客33188H多校 - Hacker

https://ac.nowcoder.com/acm/contest/33188/H

简化版描述

• 给出一个字符串 $SS$，
• 有 $QQ$ 组询问，每次给出一个字符串 $TT$，对于每个 $i\in [1,\mathrm{\mid }T\mathrm{\mid }]i\backslash in\; [1,\; |T|\; ]$，求出 $SS$的 最长的、和 $\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}T(\mathit{1},i)\backslash rm\; substring\; \backslash it\; T(1,i)$ 匹配的最长子串的长度。

解析

• 建立后缀自动机。
• 刚开始，直接字典树匹配。
• 如果失配，则沿 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边跳至其它节点，直到能继续匹配了为止。

牛客37092C - 葫芦的考验之定位子串

描述

• 给出一个只包含小写字母的字符串 $SS$。有 $QQ$ 次询问，每次询问 $SS$ 的 $\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}\text{cal}[\mathrm{l},\mathrm{r}]\backslash rm\; substring\; \backslash cal\; [l,r]$ 在 $SS$ 中的出现次数。

解析

• 后缀自动机不能直接处理指定区间子串的问题，
• 但是我们可以利用 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边的性质。
• 我们知道，$\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边指向的是 当前节点表示不了的、是当前节点能表示的子串集合的后缀。并且，若当前节点能表示的最短子串为 c+S，那么指向的节点能表示的最长子串一定为 S。
• 并且，从某个节点出发，沿着 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边走，途经的每个节点表示的都是上一个节点的后缀，并且互相没有交集，并且表示的子串集合的长度单调递减，没有交集。
• 所以，朴素的做法是：
  • 对于区间 $[l,r][l,r]$，设长度 $len=r-l+1len=r-l+1$，先定位到 $rr$ 对应的字典树节点，
  • 然后，设 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边连向的点为 $nxtnxt$
  • 如果 $maxlen(nxt)\ge lenmaxlen(nxt)\; \backslash geq\; len$，那么跳至 $nxtnxt$ ，重复上述过程。
  • 直到 ，此时当前点（非 $nxtnxt$）表示的子串集合就包含了区间 $[l,r][l,r]$ 的字符串。
• 优化方法：倍增，使用 ST 表。

建表

for (int i=1; i<=tot; i++)
    ST[i][0] = fail[i];
    
for (int i=1; i<=19; i++)
{
    for (int j=1; j<=tot; j++)
    {
        ST[j][i] = ST[ ST[j][i-1] ][i-1];
    }
}

查表

• 继续跳表的条件是 $maxlen(nxt)\ge lenmaxlen(nxt)\; \backslash geq\; len$。

for (int i=19; i>=0; i--)
{
    int nxt = ST[cur][i];
    if(!nxt)continue;
    if(max_len[nxt] >= len)
    {
        cur = nxt;
    }
}
printf("%d\n",sz[cur]);

CF149E - Martian Strings

题意

• 给定一个长度为 $n(1\le n\le 10^5)n\backslash \; \backslash \; (1\backslash leq\; n\; \backslash leq\; 10^5)$ 的字符串 $SS$，该串仅由大写字母组成
• 给定 $mm$ 个询问，每行一个字符串 $p_i(1\le \mathrm{\mid }{p}_i\mathrm{\mid }\le 1000)p\_i\backslash \; \backslash \; (1\; \backslash leq\; |p\_i|\; \backslash leq\; 1000)$，满足 $p_{i}p\_i$ 互不相同
• 对于每个询问，问是否存在 $a,b,c,da,b,c,d$ 满足$1\le a\le b<c\le d\le n1\backslash leq\; a\backslash leq\; b\; \backslash lt\; c\; \backslash leq\; d\; \backslash leq\; n$ 且 $s_a{s}_{a+1}\dots s_b{s}_c{s}_{c+1}\dots s_d=p_{i}s\_as\_\{a+1\}\backslash dots\; s\_\{b\}s\_\{c\}s\_\{c+1\}\backslash dots\; s\_d\; =\; p\_i$，即可以找到两个不相交的区间，满足这两个区间对应的子串拼起来和 $p_{i}p\_i$ 相同。

解析

• 建立两个后缀自动机，$SAM[0]SAM[0]$ 是 $SS$，$SAM[1]SAM[1]$是 $SS$ 的反串。

错误做法

• 建立后缀自动机后，对于两个自动机，查模版中的 vector 数组 $endposendpos$。
• 错误原因：内存超限。

正确做法

• 首先来看一下模版中的 vector 数组 $endposendpos$ 的求法。 end_pos[cur].push_back(pos);
  • 在插入字符时，令 $endpos[cur][0]=posendpos[cur][0]=pos$，$pospos$ 是当前插入字符的位置。
  • 全部字符插入完成后，根据拓扑序，对于每个点，向 $\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}\backslash rm\; fail$ 边连向的、拓扑序靠后的节点的 $endposendpos$ 插入该点。

for(int i=tot;i>=1;i--)
{
    int cur = rnk_len[i];
    for(auto num : end_pos[cur]) 
        end_pos[ fail[cur] ].push_back(num);
}

• 改造思路：去掉这个 vector 数组，我们只关心每个节点 $endposendpos$ 的最大值和最小值。
• 我们发现，如果对于每个节点的 $endposendpos$，只存储它 $endposendpos$ 的最大值和最小值，上述 【向拓扑序靠后的节点的 $endposendpos$ 插入该点】的代码只需改成 【向拓扑序靠后的节点的 $endposendpos$ 更新该点 $endposendpos$ 的最大值和最小值】 也可以。

for(int i=tot;i>=1;i--)
{
    int cur = rnk_len[i];
    maxi[fail[cur]] = max(maxi[fail[cur]], maxi[cur]);
    mini[fail[cur]] = min(mini[fail[cur]], mini[cur]);
//  for(auto num : end_pos[cur]) 
//  end_pos[ fail[cur] ].push_back(num);
}

牛客33186B多校 - Spirit Circle Observation

https://ac.nowcoder.com/acm/contest/33186/B

题意

• 给定一个长度为 $n(n\le 4\times 10^5)n(n\backslash leq\; 4\backslash times\; 10^5)$ 的数字串 $SS$，从中选出两个它的子串 $A,BA,B$，满足：
  • $A,BA,B$ 长度相同；
  • $B=A+1B\; =\; A\; +\; 1$。
• 若有两个子串长得相同，只要位置不同，则认为是不同的子串。

解析

初步思路

• 满足条件的 $AA$ 和 $BB$ 一定符合如下格式：
• $X+\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}+9999999999\dots X\; +\; \backslash rm\; digit\; +\; 9999999999\backslash dots$
• $X+(\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}+1)+\begin{array}{c}\underbrace{0000000000\dots }\\ \mathrm{与}\mathrm{上}\mathrm{面}9\mathrm{的}\mathrm{数}\mathrm{量}\mathrm{相}\mathrm{同}\end{array}X\; +\; \backslash rm\; (digit+1)\; +\; \backslash begin\{matrix\}\backslash underbrace\{0000000000\backslash dots\}\backslash \backslash 与上面9的数量相同\; \backslash end\{matrix\}$
• 其中，第一部分 $XX$ 和 第三部分后缀 9 和 0 可以为空。

进一步

• 枚举第一部分 $XX$

void Sol()
{
    Build();
    ll ans = 0;
    for (int i=1; i<=tot; i++)//枚举X
    {
        ans += Cal(i);
    }
    printf("%lld\n",ans);
}

• 对于每个 $XX$，通过字典树查询紧接着 $XX$ 的 $\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}\backslash rm\; digit$ 和 $\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}+1\backslash rm\; digit\; +1$。
• 设紧接着 $XX$ 的 $\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}\backslash rm\; digit$ 对应的节点为$nxt1nxt1$，$\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}+1\backslash rm\; digit\; +1$ 对应的节点为 $nxt2nxt2$。
• 如果成功同时找到了 $nxt1nxt1$ 和 $nxt2nxt2$，那么对答案的贡献为 $cnt\times sz[nxt1]\times sz[nxt2]cnt\backslash times\; sz[nxt1]\backslash times\; sz[nxt2]$，其中 $cnt=max\mathrm{\_}len[X]-max\mathrm{\_}len[fail[X]]cnt=max\backslash \_len[X]-max\backslash \_len[fail[X]]$
• 沿着字典树接着往下走，$nxt1nxt1$ 继续搜寻 9，$nxt2nxt2$ 继续搜寻 0。
• 如果成功同时找到，那么对答案的贡献为 $cnt\times sz[nxt1]\times sz[nxt2]cnt\backslash times\; sz[nxt1]\backslash times\; sz[nxt2]$（同上）。
• 直到某一个找不到接下来的 9 或 0，宣告停止。

ll Cal(int cur)
{
    ll cnt = max_len[cur] - max_len[ fail[cur] ];
    if(cur==1) cnt = 1;
    
    ll sum = 0;
    for (int i=0; i<=8; i++)
    {
        //对于每个 X，通过字典树查询紧接着 X 的 digit 和 digit+1。
        int nxt1 = trie[cur][i];
        int nxt2 = trie[cur][i+1];
        
        if(nxt1==0 || nxt2==0)continue;
        
        //如果成功同时找到了 nxt1 和 nxt2，那么对答案产生贡献
        sum += cnt * sz[nxt1] * sz[nxt2];
        
        while (1)
        {
            nxt1 = trie[nxt1][9];
            nxt2 = trie[nxt2][0];
            
            if(nxt1==0 || nxt2==0)break;
            
            //如果成功同时找到了 nxt1 和 nxt2，那么对答案产生贡献
            sum += 1ll * cnt * sz[nxt1] * sz[nxt2];
        }
    }
    return sum;
}

答疑

• 这样会不会造成计算重复？
  • 不会。因为我保证在第一部分和第三部分之间有 $\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}\backslash rm\; digit$。
• 为什么贡献是 $cnt\times sz[nxt1]\times sz[nxt2]cnt\backslash times\; sz[nxt1]\backslash times\; sz[nxt2]$？
  • 因为我枚举的是后缀自动机的每个节点，枚举每个节点能保证，所有子串必然枚举恰好一次。
  • 设这个原串总共有 $sumsum$ 个子串（本题规定相同但位置不同的子串不算同一个，那么$sum=C_n^{2}sum=C\_\{n\}^\{2\}$ ）对于后缀自动机的某个节点 $ii$，它能表示的子串集合数量为 $cn{t}_{i}cnt\_i$，那么 $\sum cn{t}_i=sum\backslash sum\; cnt\_i=sum$。