字符串全家桶

2023年12月06日算法学习约7.8k字预计需要30分钟

@[toc]
~~现已加入KFC豪华套餐~~

<从零开始的字符串学习指南>

本文综合了@adolphshi所有学过的字符串算法，会一直不定期更新。
~~但是这个人太懒了，什么时候弃坑了也不一定~~

<前言、统计与目录>

<统计>

开坑日期2023-11-2
hash 完成日期 unknown
trie 树完成日期 unknown
KMP 完成日期 2023-11-30

<前言>

最近看了很多的字符串算法，于是就想写一篇博客记录下来。也希望这篇博客可以帮助一部分人。
也是为了不被卡在需要对字符串进行处理的题上.
这里的字符串算法有极大概率没有代码,代码和例题可能完结以后再进行添加.
这里默认 $S$ 为一个字符串， $S*i$ 为 $S$ 的第 $i$ 个字符， $S*{i,j}$ 为 $S$ 的 $i$ ~ $j$ 的子串， $n$ 为字符串 $S$ 的长度。

在此处,若无提前声明,默认字符串的下标是从 $1$ 开始的.

< hash >

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围——OI wiki

hash(哈希) 其实一点也不难理解,通俗来讲,就是将一个字符串压缩成一个 $k$ 进制(通常为 $31$ 或 $113$ )的数字,然后可以做到 $O(1)$ 进行比较(或进行存储).当然,若是直接压缩成一个 $k$ 进制数字,通常会爆long long,因此我们可以对一个大质数 $p$ 取模(当然也可以自然溢出).

但是若对数字取模后,数字会重复(即有两个不同的字符串对应的数字相同),这种情况被称为哈希冲突.处理哈希冲突的方法有二:

拉链法(不推荐)
进行多次不同的哈希

因为我们将字符串看成了一个 $k$ 进制再模 $p$ 的整数,所以我们可以使用类似前缀和的思想来进行快速的求出子串的哈希值.

当我们发现可以将一个字符串看成一个 $k$ 进制字符串时，就有了以下操作：

$1.hash*{i \cdots j} = (hash*{i\cdots j-1}\times k+s_{j})-\mod p$

$2.hash*{i \cdots j} = (s*{i}\times k^{j-i}+s*{i+1}\times k^{j-i-1}+\cdots+s*{j-1}\times k^1+s_j\times k^0)\mod p$

(以上均有特殊情况 $i=1$ ) (非常重要)

$3.hash*{i+1\cdots j} = (hash*{i\cdots j} -s_i\times k^{j-i}+p)\mod p$

$4.hash*{i\cdots j} = ((hash*{i\cdots t}\times k^{j-t})\mod p+hash_{t+1\cdots j})\mod p$

$5.hash*{i\cdots j} = ((hash*{1\cdots j}-(hash_{1\cdots i-1}\times k^{j-i+1})\mod p)\mod p$

(最后一条和倒数第二条最重要，因为它能使我们利用类似前缀和的方式求解哈希)

图片here

<trie树>

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。——OI wiki

trie 树是字符串算法中非常重要的一个算法,因为后面的自动机都需要用到 trie 树.

<普通trie树>

话不多说，先放图

ps：也是oi-wiki的图

其中根节点到各个节点的路径代表一个字符串,节点之间的连边代表一个字符,但是不难发现，若是下面两组数据

aa 
aba
ba
caaa
cab
cba
cc

aa 
aba
ba
caaa
cab
cba
cc
c

便会发现两组数据建出来的树相同.此时我们只需将每一个字符串的末尾打上标记即可.

加粗即为末尾标记.

其中trie树最为常见的操作是查找字符串~~(不然叫什么字典树啊)~~,方法也很简单,就是顺着路径向下找就行了,若找到的最后一个点有末尾标记,便可以找到.

<01 trie>

顾名思义,就是只有01两个分支的trie树.用01trie树可以很方便地求最大异或值,维护异或和等操作.

<01 trie 维护最大异或和>

其实不难,因为最大异或和就是希望找一个数字与另外一个数字使其尽可能不同,到 01 trie 上就是尽可能地向另外一条边走即可.

在此时的01 trie上可以再进行其他的修改操作,这里就不再赘述,感兴趣的读者自行探索.

<01 trie 当平衡树>

拿 01 trie 当普通平衡树是最好不过的了,它码量小,易于理解.

实现就是将每一个数字转成二进制再由高位到低位放入 01 trie 中,trie 的每一个节点都再维护一个子树大小即可.它基本可以完成普通平衡树所做的所有内容,就是所需空间大小有点大.

<可持久化 trie 树>

没什么好讲的,就是每将一个 trie 树更新是再进行路径复制即可,代码(按理来说)与主席树没有什么区别.

< KMP >

因此 Knuth–Morris–Pratt 算法（简称 KMP 算法）用 O(n + m) 的时间以及 O(n) 的内存解决了在字符串中查找子串的问题.——OI wiki

KMP 算法是一个快速匹配子串（匹配的串）与母串（被匹配的串）的算法,它的核心思想就在于利用字符串的重复减少在匹配时的向后跳跃(比较难表述,学完就知道了).

<前缀函数>

前缀函数(在OI中常用为 next 数组)是一个记录前缀后缀相同的最长的字符串的个数的函数.

前缀函数是 KMP 的一个非常重要的前置芝士,因为 KMP 的核心就在于利用前缀函数减小时间复杂度.

前缀函数如图:

此处的橙色箭头所指的位置的前缀函数的值为2,因为蓝色部分与红色部分的字符串是相同的,也是最长的字符串.

但是正常情况下,用暴力的方法去求单个字符的前缀函数是 $O(n)$ 的,不过我们可以利用前缀函数的一些性质来做到 $O(n)$ 递推地预处理出字符串每一个字符的前缀函数.

在 KMP 中用到的 next 数组,一般都是不包含自身的最长相同前后缀,且通常为相同的长度 $+1$ ,因此我们在接下来的预处理 next 数组的时候也按照此规则进行.

我们规定空字符串的最长相同前后缀为0.
递推过程可以用下面一幅图来讲：
我们要进行处理绿色的地方的 next 数组的值,我们比对两个黄色指针所指的地方,若两个黄色指针所指的字母相同,则先同时加一,再将第一个黄色下表当做绿色位置的 next 数组的值.
若不同,则第一个黄色指针跳回上图中蓝色位置(是那个数的 next 值)再进行下一轮比对.
这里的正确性请读者自证.

一个结论：当这个字符串有一个长度为 $k$ 的公共前后缀，必然会有一个长度为 $|S|-k$ 的周期

在预处理出 next 数组后,接下来就是进行 KMP 了.

<KMP 算法>

在 KMP 算法之前,请各位读者回想一下朴素的字符串匹配:
两个下标字符相同时同时加一,不同时一个回到子串开头,一个回到母串开始匹配的位置加一，再继续进行下一轮匹配。

而 KMP 算法的思想就是让母串的下标不向回退,这样就可以做到 $O(n)$ 匹配字符串了.但是这样子串的下标肯定是不能再向前调回刚开始的位置了,显然正确性是没有保障的.
这时候回想一下我们的 next 数组~~(其实也不用回忆了,刚看完)~~, next 数组处理的是最长相同的前后缀因此我们直接跳至该位置的 next 数组指向的下标即可.

还是以这张图为例,当我们在倒数第二个字符处失配时,可以发现,他前面的九个字符与开头的九个字符完全相同,那么这九个字符就不需要进行匹配了(因为匹配到这一个字符时除了这一个字符,前面的字符都应该相等,那么就是后缀与前缀相同的部分就无需再进行匹配了),这样就保证了正确率.

<KMP 算法的可视化>

这是一个附加的内容,因为我认为我的KMP讲的不太好(本来是有动图的,但是存动图的图床寄了QAQ),很难让读者理解(包括复习时的我),特此,在下面添加一个可以亲自操作的 KMP 可视化的网站:
link
这个可视化的网站与我所讲的还是有一些出入,原因包括但不限于下标问题,一开始可能会对一部分人造成一定的误解,请谅解.

<AC自动机>

AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的自动机，用于解决多模式匹配等任务。——OIwiki

AC自动机并不是字面意义上可以让你自动AC题的东西，而是一种算法，用来解决多个模式串匹配一个母串的算法，举个例子：

母串
adolphshi
匹配的模式串
adolph
shi
adols
phs

如果拿KMP来处理的话，设一个母串的长度为 $n$ ，每一个模式串都是 $O(n)$ 的时间复杂度，总时间复杂度就是 $O(n^2)$ ,然而使用AC自动机的总时间复杂度却是 $O(n)$ 的。可以看出非常高效。

AC自动机的流程简单来说就是：

整个模式串变成一棵trie树。
在这棵trie树上求出失配指针。
将母串在这个trie树（其实现在就是AC自动机了）上跳点即可。

<构建trie树>

这个就是一颗正常的trie树，trie树中的字符串都是一个需要匹配的字符串。不过为了接下来好理解，我们需要把它想象成一个图，对于每一个节点，它与其他节点的连边表示到它时后面再加哪一个字符可以到达那个节点。

<失配树和失配指针>

与KMP相同的，AC自动机中也有一个与next数组一样重要的东西——失配指针（又称fail指针）。它的内容也与next数组类似，都指向最长的与前缀相同的后缀，但fail指针可以指向任意一个trie树中的节点。（不理解不要紧，后面会解释）

可以得到，每一个trie树中的节点都会有一个fail指针，只保留这些指针，就会形成一棵树，叫做失配树（fail树），这在有些题中非常常用。（至于为什么是棵树，我就不证了~~太菜了不会~~）

<fail指针构建>

这个过程也可以类比 KMP 中next指针的构建过程，找到一个当前点 $p$ 构建它的fail指针过程如下（ $p$ 在trie树上的父亲为 $q$ , $p,q$ 之间的边为 $c$ ,所有深度小于 $p$ 的点的fail指针已经构建完成）：

如果 $q$ 的fail指针所指向的节点 $fail\[q]$ 也有一条 $c$ 的边，则将当前节点的fail指针指向 $fail\[q].ch\[c]$ 其中 $ch\[c]$ 为当前节点出边为 $c$ 的孩子。
如果 $fail\[q]$ 没有为 $c$ 的出边，就找到 $fail\[q]$ 的fail指针所指向的 $fail\[fail[q]]$ ,并重复1的判断，直到找到fail指针为止。
如果到达根结点，就将 $fail\[p]$ 指向根节点。

对于一棵trie树（由aa aba ba c构成），其fail指针构建如下：

黑边：trie树的边

蓝边：fail指针

绿点：已经求完fail指针的点

黄点：当前点

小青箭头：相同的c边

<AC自动机-完全体>

在上一个图中，我们会发现，在有些时候跳fail指针需要跳到根节点，看起来很浪费时间（事实上也是），我们能不能让构造fail指针“一步到位”呢？

答案显然是可以的（~~要么然我也不会问这个问题了~~），解决方法就是将原先的trie树改造，添加一些新的边，使他每一次找fail直接就能找到相同的出边。
但是怎么添加新边呢？我们假想这个节点有一个出边为 $c$ 的一个节点 $x$ ，让它的fail指针所指的节点成为这个节点的为 $c$ 的出边即可。

改造完的trie树（其实是trie图）就是大名鼎鼎的AC自动机啦！

我们采用BFS的方式去构建AC自动机具体过程见下面的动图和最后的代码：(图片较大，等待时间可能较长)

code

因为AC自动机也是刚刚学，所以这边给出代码加深印象并辅助理解：

需要的数组、结构体

struct ss
{
  int tg,nex[30],fail;\\从左到右分别为：末尾标记、出边、失配指针
}tr[maxn];\\字典树（图）
int n,ans[maxn],cnt;\\cnt 为内存池，ans用于存储答案
int head[maxn],to[maxn],nex[maxn],tot;\\构建fail树所需的链式前向星

字典树的构建

\\这个其实没什么好说的，就和正常的字典树构建一样
void insert(char *s)
{
  int now=0;
  _F(i,1,strlen(s+1))
  {
    if(!tr[now].nex[s[i]-'a'+1])
      tr[now].nex[s[i]-'a'+1]=++cnt;
    now=tr[now].nex[s[i]-'a'+1];
  }
  tr[now].tg++;
}

bfs构建fail指针

queue<int > q;
void add(int a,int b)
{
  to[++tot]=b;
  nex[tot]=head[a];
  head[a]=tot;
}
void bfs()
{
  _F(i,1,26)
  {
    if(tr[0].nex[i])\\如果存在
    {
      fail[tr[0].nex[i]]=0;\\预先处理出根节点儿子的fail指针
      q.push(tr[0].nex[i]);
    }
  }
  while(!q.empty())
  {
    int t=q.front();
    q.pop();
    _F(i,1,26)
    {
      if(tr[t].nex[i])\\如果存在
      {
        fail[tr[t].nex[i]]=tr[fail[t]].nex[i];\\设置fail指针为father的fail指针的儿子
        q.push(tr[t].nex[i]);
      }
      else
        tr[t].nex[i]=tr[fail[t]].nex[i];\\假想一个新节点，并让它的fail边成为当前节点的出边
    }
  }
  _F(i,1,cnt) add(fail[i],i);\\构建fail树
}

AC自动机处理询问

void ac_ask(char *t)
{
  int l=strlen(t+1);
  int now=0;
  _F(i,1,l)
  {
    now=tr[now].nex[s[i]-'a'+1];\\因为我们预先处理出了如果下一个字符是什么，我么将跳到什么位置，因此我们在这里直接向下找即可
    if(tr[now].tg)\\ 这里不同的写法会有不同的效果，我这里是【模板】AC自动机（简单版）中的要求
      ans[now]=tr[now].tg;
  }
}

fail树自底向上处理最终结果

void dfs(int x)
{
  TF(i,x,y)\\遍历所有出边
  {
    y=to[i];
    dfs(y);\\dfs并累加子树
    ans[x]+=ans[y];
  }
}

<后缀自动机>

~~噔噔咚~~,开始上强度了.

后缀自动机(suffix automaton 以下简称 SAM)与后缀数组,后缀树类似,都是用来维护子串信息的数据结构,它能解决最经典的问题就是本质不同的子串个数.时间与空间复杂度均为 $O(n)$ ,那至于为什么我没写后缀树和后缀数组,~~后缀数组太难了不会~~.

后缀自动机的强大之处不仅在于能够 $O(n)$ 处理子串问题,还在于它是在线的,并且加以扩展之后可以成为处理多个字符串的广义后缀自动机

首先我们要了解后缀自动机的结构.我们刚才说了,我们可以把整个自动机想成一个地图,每一个点是状态,例如AC自动机的节点就代表的是匹配的状态,每一条边就是转移(如果对DP比较熟悉,那么很快就能意识到这很像DP),例如AC自动机中的转移边就是下一个字符是什么就转移到什么节点.而后缀自动机中,一个节点代表一类后缀,而从原点到节点的每一条路径就是那个节点所含有的一条后缀.

后缀自动机就是通过压缩了相近的子串来做到 $O(n)$ 处理子串问题.

<前置知识>

为了更好理解SAM,我们还需要一点前置知识(但是很难理解,如果不能理解就可以直接跳至构造~~背了再理解~~).这边建议自己拿张纸和笔自己推一下.

我们定义一个字符串 $s$ 的子串 $t$ (默认非空子串),在整个 $s$ 中结束的位置的集合称之为 $\text {endpos(t)}$ 例如 $\textbf{abcab}$ 中 $\text{endpos(\textbf{ab})}={2,5}$

我们注意到,有一些子串的 $\text{endpos()}$ 可能一样,例如上文中 $\text{endpos(\textbf{ab})=endpos(\textbf{b})}$ ,我们称这些子串所构成的集合称之为一个等价类,而我们的SAM就是在等价类上做手脚.

我们由 $\text{endpos()}$ 的定义可以得到一些性质:

性质1:如果两个子串 $t_1,t_2(|t_1|\leq |t_2|)$ 的 $\text{endpos()}$ 相同,当且仅当 $t_1$ 作为 $t_2$ 的后缀并且没有在原串中额外出现

证明不难,画个图自己理解就可以了.

性质2 :对于两个子串 $t_1,t_2(|t_1|\leq |t_2|)$ 如果 $t_1$ 不为 $t_2$ 的后缀,那么它们的 $\text{endpos()}$ 集合交集为空,否则 $\text{endpos}(t_2) \subseteq \text{endpos}(t_1)$ 注意包含关系

证明就是如果两个 $\text{endpos()}$ 有交集,那么就一定能够有一个公共的结束位置,也就有一个公共的后缀,又因为字符串不能分叉,所以一个肯定是另一个的后缀,那么 $\text{endpos}(t_2) \subseteq \text{endpos}(t_1)$ (自己画个图方便理解)

性质3 :考虑一个 $\text{endpos}$ 等价类，将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间 $[x,y]$ 。

如果 $\text{endpos}$ 等价类中只包含一个子串，性质显然成立。现在我们来讨论子串元素个数大于 $1$ 的等价类。

性质3证明

由性质 1，两个不同的 $\text{endpos}$ 等价的字符串中，较短者总是较长者的真后缀。因此，等价类中没有等长的字符串。

记 $w$ 为等价类中最长的字符串、 $u$ 为等价类中最短的字符串。由性质 1，字符串 $u$ 是字符串 $w$ 的真后缀。现在考虑长度在区间 $[|u|,|w|]$ 中的 $w$ 的任意后缀。容易看出，这个后缀也在同一等价类中，因为这个后缀只能在字符串 $s$ 中以 $w$ 的一个后缀的形式存在（也因为较短的后缀 $u$ 在 $s$ 中只以 $w$ 的后缀的形式存在)。因此，由性质 1，这个后缀和字符串 $w$ 的 $\text{endpos}$ 相同。

by OI-wiki

简单理解就是最长的和最短的中间的 $\text{endpos}$ 集合相同

所以我们可以尝试以等价类为基准分类子串,并且记录每一个等价类中最长的子串为 $\text{maxlen(t)}$ 长度为 $\text{len(t)}$

后缀链接

我这里说一下我的理解,如果有错误请在下面指出:

我们发现,通过以上三个性质,对于 $s$ 所有等价类的 $\text{endpos}$ 集合要么然不相交,要么然包含,(我记得这是不是叫做不交集).根据这种集合的性质,我们可以根据包含关系建出一棵树(一定是一棵树,其中根节点为我们虚拟出的超级根节点,要么然就是一颗森林),我们定义这棵树叫做后缀链接树,所有的父子关系(子向父)叫做后缀链接.

我们发现,由于 $\text{endpos}$ 的包含关系,我们后缀链接树上的父亲节点一定是儿子节点的一条后缀 (性质2) 并且,每一个父亲的等价类中最长的子串长度为儿子节点的等价类中最短子串的长度减一(也就是在一条链上的子串长度是"连续的").

连续性证明

我们设儿子节点的等价类的最短子串为 $t$ ,它的长度减一的后缀为 $u$ ,由等价类的定义以及性质2可得: $\text{endpos}(t) \subseteq \text{endpos}(u)$ 又由后缀链接树的定义可得 $u$ 所在的等价类就是父亲节点所代表的等价类.且能得到 $u$ 是父亲等价类中最长的子串.

SAM的构造

学完前置知识之后,就能够开始构造SAM了,前面说过了SAM是在线算法,因此我们是一个字符一个字符地向SAM里面插入的.设我们新添加的字符为 $c$ ,那么整个插入过程就是为 $c$ 找到它的后缀链接(也就是后缀链接树上的father,下文使用 $\text{fa}$ 表示).其流程如下:

设 $lst$ 为添加新的字符之前的状态,我们建一个状态,叫做 $cur$ ,并将 $\text{len}(cur)=\text{len}(lst)+1$ (因为当前最长的子串是整个串)
我们从 $lst$ 开始,一直向上跳 $\text{fa}$ 直到找到第一个存在 $c$ 这条转移的状态,与此同时,将经过的状态新建一条 $c$ 的转移向 $cur$
如果当前的节点跳到了最上方的原点,这就说明原串中还没有出现过 $c$ ,于是我们给所有的后缀都填上了 $c$ 的转移,并且直接将 $cur$ 的 $\text{fa}$ 指向原点.并直接跳到最后一步.
如果找到了状态 $p$ ,设其沿 $c$ 转移后的状态为 $cp$ ,接下来继续分讨
如果 $\text{len}(p)+1=\text{len}(cp)$ ,注意到因为 $p$ 是由我们跳后缀链接得到的,因此它所代表的子串(就是等价类中最长的子串)一定是我们加 $c$ 之前的字符串的后缀,那当前这个判断其实就是相当于是 $cp$ 所代表的字符串就是通过 $p$ 转移而来的.那么我们直接将 $cur$ 的后缀链接指向 $cp$ 即可.直接跳到最后一步.
否则情况就比较复杂了,这个条件就意味着 $cp$ 所代表的字符串不是通过 $p$ 转移来的,而是从别的地方转移过来的,只不过 $p+c$ (就这么写吧)与 $cp$ 所代表的字符串恰好在同一个等价类中.
此时 $cp$ 的等价类中会有不是 $c$ 加之前的后缀的部分,所以我们要分裂,我们将 $cp$ 复制出来一个 $np$ ,并将 $\text{len}(np)$ 设成 $\text{len}(p)+1$ 此时 $np$ 代表之前 $cp$ 中可以从 $p$ 转移过来的部分, $cp$ 代表不能从 $p$ 转移过来的部分,那我们就可以将 $cur$ 的后缀链接指向 $np$ 了,又因为 $np$ 同时也是 $cp$ 的后缀,因此也将 $cp$ 的后缀链接指向 $np$
复制之后,因为现在的 $cp$ 代表的是不能由 $p$ 转移到的地方,因此我们要跳 $p$ 的后缀链接将每一个指向 $cp$ 的转移重定向到 $np$
最后将 $las$ 设成 $cur$

我们而可以根据这个过程模拟,下面放出一个 $\text{aababa}$ 的SAM构建的视频方便理解:

实现

我们可以根据刚才的过程列出我们在构造SAM过程中需要用到的变量:

struct SAM
{
	int ch[26];\\转移
	int len,fa;\\最长子串,后缀链接
}sam[maxn];\\写在结构体中方便复制
int lst=1,cnt=1;

然后我们就可以根据刚才说的过程写出对应代码了:

#define len(x) sam[x].ln
#define fa(x) sam[x].fa
#define ch(x,y) sam[x].ch[y]
int insert(int x)
{
	int p=las,cur=++cnt;
	len(cur)=len(p)+1;
	while(p&&!ch(p,x)) ch(p,x)=cur,p=fa(p);
	if(!p)
		fa(cur)=1;
	else
	{
		int cp=ch(p,x);
		if(len(cp)==len(p)+1)
		{
			fa(cur)=cp;
		}
		else
		{
			int np=++cnt;
			sam[np]=sam[cp];
			len(np)=len(p)+1;
			fa(cur)=fa(cp)=np;
			while(p&&ch(p,x)==cp) ch(p,x)=np,p=fa(p);
		}
	}
	return las=cur;
}

当然,我们现在拥有了SAM,他可以做很多的操作,但是在做这些操作之前,我们应当还需要了解一个非常重要的数组: $\text{siz}$ 它代表着当前状态所代表的 $\text{endpos}$ 集合的大小.有了这个我们就可以统计子串在母串中出现的次数.

那它怎么求呢?我们知道,正常插入(不是复制出来)的字符的 $\text{endpos}$ 集合大小为 $1$ ,并且对于每一个节点当前节点的 $\text{endpos}$ 集合是它在后缀链接树上的所有儿子并上它自己的集合,那么我们就应该能够得到集合大小其实就应该是后缀链接树上的子树求和,对于每一个插入产生的状态其大小设为 $1$ .

显然我们可以建出这个树,然后直接 dfs.不过我们发现如果按 $\text{len}$ 大小排序,那么我们得到的就应该是一个拓扑序,基数排序然后倒着操作即可.

void sort()
{
    _F(i,1,cnt) t[len(i)]++;
    _F(i,1,cnt) t[i]+=t[i-1];
    _F(i,1,cnt) A[t[len(i)]--]=i;
    F_(i,cnt,1)
    {
        int x=A[i];
        siz[fa(x)]+=siz[x];
    }
}

例题后面再补.

广义SAM

~~错解重灾区~~不过现在好像都改回来了.

没错你没听错,这个东西是可以同时维护多个字符串的.

首先我们有一个错误但是是顺理成章的算法:每一次将 $lst$ 制成 $1$ ,但是由于广义SAM中可能会已经创建了这个节点,这样就会导致插入许多的空状态导致出问题.

所以我们需要加特判:

如果当前状态并没有创建,就和普通的SAM一样构建即可
如果当前节点存在,且 $\text{len}(lst)+1=\text{len}(cur)$ 那么就说明转移是相同的,直接返回即可
如果 $\text{len}(lst)+1 \neq \text{len}(cur)$ 那么说明我们需要拆分节点,拆分过程是与SAM拆分是一样的,不过还要有以下几点注意:
1. 根据我们对分裂的理解,当前分裂出来的状态的代表的子串就应该相当于我们新加的字符串.那么我们设 $lst$ 时候就应该设成我们分裂出的节点.
2. 因为我们已经有了 $c$ 转移的状态,因此我们在一开始就不应该建立那个新的节点,所以设 $\text{fa}$ 时只需要将旧节点的 $\text{fa}$ 指向分裂出来的节点即可.

此外,在广义SAM中 如果你在构建过程中记录了 $\text{endpos}$ 的大小,那么你应该对于每一个字符串都单独记录一个,因为一个节点压缩了多个字符串的信息. 详见实现.

下面给出一个广义SAM构建的动图:

实现

如果我刚才讲述的没有理解上的障碍并且你也理解了SAM的话,那么你就应该能写出代码:

#define len(x) sam[x].len
#define fa(x) sam[x].fa
#define ch(x,y) sam[x].ch[y]
#define m 5
struct SAM
{
    int ch[27],fa,len;
}sam[maxn<<1];
int las=1,cnt=1,siz[m][maxn<<1],tp=0;\\每一个字符串单独开一个
void nl(){las=1;tp++}\\新建一行
int insert(int x)
{
    if(ch(las,x))
    {
        int lp=las,cp=ch(lp,x);
        if(len(lp)+1==len(cp))
        {
            siz[tp][cp]++;
            return las=cp;
        }
        else
        {
            int wp=++cnt;		
            sam[wp]=sam[cp];len(wp)=len(lp)+1;
            fa(cp)=wp;
            while(lp&&ch(lp,x)==cp) ch(lp,x)=wp,lp=fa(lp);
            siz[tp][wp]++;
            return las=wp;
        }
    }
    int lp=las,np=++cnt;
    len(np)=len(lp)+1;
    while(lp&&!ch(lp,x)) ch(lp,x)=np,lp=fa(lp);
    if(!lp)
        fa(np)=1;
    else
    {
        int cp=ch(lp,x);
        if(len(cp)==len(lp)+1)
        {
            fa(np)=cp;
        }
        else
        {
            int wp=++cnt;
            sam[wp]=sam[cp];
            len(wp)=len(lp)+1;
            fa(np)=fa(cp)=wp;
            while(lp&&ch(lp,x)==cp) ch(lp,x)=wp,lp=fa(lp);
        }
    }
    siz[tp][np]++;
    return las=np;
}
int t[maxn<<1],A[maxn<<1];
void sort()
{
    _F(i,1,cnt) t[len(i)]++;
    _F(i,1,cnt) t[i]+=t[i-1];
    _F(i,1,cnt) A[t[len(i)]--]=i;
    F_(i,cnt,1)
    {
        int x=A[i];
        _F(j,0,m-1)
        	siz[j][fa(x)]+=siz[j][x];
    }
}
void getans()
{
    //答案
}

注意:因为我们写的是正确的广义SAM,因此我们依旧可以使用正常的基数排序来解决 $\text{endpos}$ 的大小的问题.

例题后面再给.

参考文献

OIwiki -后缀自动机

史上最通俗的后缀自动机详解

【学习笔记】字符串—广义后缀自动机-by 辰星凌

文章分类

一言

文章归档

最新文章