后缀自动机&广义后缀自动机

后缀自动机(SAM)

0x01 简单定义

对于一个自动机$M$和字符串$S=s_0s_1s_2...s_{n-1}$。令$S_i$为字符串$S$从第$i$位开始的后缀,即$S_i=s_is_{i+1}s_{i+2}...s_{n-1}$,如果自动机$M$可以接受所有可能的$S_i$及其子串,并排斥其他所有的字符串,那么就称这个自动机$M$为字符串$S$的后缀自动机。

后缀自动机全称为Suffix Automaton,缩写为SAM。后缀自动机非常强大,能解决所有后缀数组可以解决的问题,又因为其将字符串问题转换成了在DAGDirected Acyclic Graph,有向无环图)上的图论问题,所以一般来讲比后缀数组容易理解和上手。

0x02 前置知识

1. Endpos集合的定义

对于字符串$S$的一个子串$S_{ij}$,即$S_{ij}=s_is_{i+1}s_{i+2}...s_j$,把它在$S$中出现的所有结束位置保存在一个集合中,这就是Endpos集合

如:$S=ababbaab$,所以$Endpos(ab)=\{1,3,7\},Endpos(b)=\{1,3,4,7\}$。

2. Endpos集合的性质

(1) 如果两个子串的Endpos集合相同,那么其中一个子串必然是另一个子串的后缀

这个性质是非常显然的,只要举几个例子即可,或者我们可以反证一下:

假设两个子串的Endpos集合相同,而他们互不为后缀。由于Endpos集合存储的是结束位置,既然互不为后缀,那么结束位置肯定会出现不相等的地方,假设矛盾,原命题成立。

(2) 对于任意两个子串$S_i$和$S_j$,且$|S_i|\leq|S_j|$,要么$Endpos(S_j)\subseteq Endpos(S_i)$,要么$Endpos(S_i)\cap Endpos(S_j)=\varnothing$

这个性质其实是性质(1)的逆命题,也可以用(1)中类似的方法证明。

3. Endpos等价类的定义

对于所有Endpos集合相同的子串,我们将其归为一个Endpos等价类。

如:$S=ababbaab$,且$Endpos(abab)=\{3\},Endpos(bab)=\{3\}$,所以$Endpos(abab)=Endpos(bab)$,所以子串$abab$和子串$bab$属于同一个Endpos等价类。

4. Endpos等价类的性质

(1) 对于任意一个Endpos等价类,将其中的子串按长度降序排列,则每个子串的长度均为上一个子串长度减1,且为上一个子串的后缀

这个性质简单来说就是每个Endpos等价类中所有的子串的长度覆盖区间是连续的。

由Endpos集合性质(1)以及长度降序可知,显然每个子串是上一个子串的后缀。对于长度严格等差递减,可以这样想:

假设有一个子串$S$,它的Endpos集合为$A$。将$S$依次从前面删除一个字符,首先能保证所以新得到的字符串$S'$都是$S$的后缀,每个$S'$都有自己的Endpos集合。如果$S'$的Endpos集合仍然等于$A$那么我们继续删除直到为空,如果$S'$已经不属于等价类$A$了,那么$S'$自己的所有后缀都不可能属于等价类$A$,因为此时$S'$所属的等价类$B$必定至少比等价类$A$多一个元素,且有关系$A\subseteq B$,因为此时$S'$处了可以在$S$中以后缀的形式出现,还可能在其他位置上出现。

(2) Endpos等价类的数量级为O(n)

这个性质其实在SAM中并不是那么重要,也不会对解题有什么帮助,所以在这里不会对其进行证明,但是这条性质的一个重要的结论是:对于一个长度为$len$的字符串,其SAM的节点数量至少要有$2len$个。

5. Parent Tree的定义

Parent Tree这个结构是基于Endpos等价类的划分树结构。在前面我们已经了解了Endpos集合的几个性质,因为对于字符串所有的Endpos集合都有不是子集就是无交集的情况,所以对于每一个Endpos集合所属的Endpos等价类,都存在一种方法可以将其划分成另外几个存在的Endpos等价类,直到无法划分为止。

需要注意的是,在SAM中,一个Endpos集合的所有划分的并集是其子集,也就是说可能存在Endpos集合所有划分的并集不等于其本身的情况

如对于字符串$S=aababa$,其各不同子串的Endpos列表及其所属Endpos等价类如下:

$S'$$Endpos(S')$Endpos等价类
$\varepsilon$$\{0,1,2,3,4,5\}$0
a$\{0,1,3,5\}$1
aa$\{1\}$2
aab$\{2\}$3
aaba$\{3\}$4
aabab$\{4\}$5
aababa$\{5\}$6
ab$\{2,4\}$7
aba$\{3,5\}$8
abab$\{4\}$5
ababa$\{5\}$6
b$\{2,4\}$7
ba$\{3,5\}$8
bab$\{4\}$5
baba$\{5\}$6

可知该字符串一共存在9个Endpos等价类,我们再按照Endpos等价类来归类这些子串:

Endpos等价类$Endpos(S')$$S'$
0$\{0,1,2,3,4,5\}$$\varepsilon$
1$\{0,1,3,5\}$a
2$\{1\}$aa
3$\{2\}$aab
4$\{3\}$aaba
5$\{4\}$aabab,abab,bab
6$\{5\}$aababa,ababa,baba
7$\{2,4\}$ab,b
8$\{3,5\}$aba,ba

我们从空串$\varepsilon$开始划分它的Endpos集合,SAM的划分过程就是不断地往串的前面加字符

从$\varepsilon$开始,可以添加字符得到a和b,我们这时候查表可以发现$Endpos(\varepsilon)$刚好能划分成$Endpos(a)$和$Endpos(b)$。

我们再从a开始添加字符,发现$Endpos(a)$又可以尽可能大地划分为$Endpos(aa)$和$Endpos(ba)$,此时会发现$Endpos(a)$中的元素0不存在其划分的并集中,这不重要,因为我们在前面就已经说明了原因,我们只需要保证a是划分代表的字符串的后缀,且划分的Endpos集合尽量大就行了。

我们就如此进行划分,最后能得到这么一棵树:

这就是我们所要找的Parent Tree,它表明了各个Endpos等价类之间的覆盖从属关系(父子关系),而每一条从儿子连接到父亲的边,我们称为后缀链接

6. Endpos等价类在Parent Tree上的关系

对于一个Endpos等价类$A$,其中包含了若干个字符串,其中最长串的长度设为$maxLen(A)$,最短串的长度设为$minLen(A)$,等价类A在Parent Tree上的父节点为等价类B,则有:$minLen(A)=maxLen(B)+1$。

这个性质我们在上文的表中一查就能发现了,在一个等价类的最长串前面增加一个字符,那它必然属于儿子等价类中,而且是作为最短串存在的。

那么我们不需要在Parent Tree的每个节点里存储Endpos等价类的所有子串信息了,我们只需要记录该等价类最长串的长度$len$,而最短串的长度就可以用父节点的$len$增加1得到。

我们在上面的树形图中标注出最长串,就可以得到如下的新图:

7. 将Parent Tree上的节点通过连接构造就能得到SAM

刚刚还在讲Parent Tree,现在突然转到SAM,这一步是不是有点快了

这是最后一个前置知识。将Parent Tree的根节点作为SAM的起始节点,将整个字符串所属的节点及其所有的,不包括起始节点父节点作为SAM的终止节点,其他的节点都是SAM的一个状态。

我们在Parent Tree上建边,使每个Endpos等价类中的所有字符串都可以转移到达,就得到了SAM。

至于我们构造SAM为啥要经过Endpos集合、Endpos等价类和Parent Tree,绕了这么一大圈,是因为我们要满足SAM的几个条件:有向无环图和规模最小。

我们构造出Endpos集合与Endpos等价类,并赋予他们父子关系,产生Parent Tree,是为了满足有向无环图的要求,因为一个被父等价类所包含的等价类,它一定不可能存在一个转移回到它的父等价类中。而由于Endpos等价类的存在,相当于我们把字符串的所有可能转移全部压缩到了数个等价类中,这又可以满足规模最小,即状态最少的要求。

0x03 构造SAM

老规矩,先放代码:

// 字符串长度
#define MAX_N 114514
// 字符集大小
#define MAX_M 26

// 后缀自动机结构
struct SAM {
    struct Node {
        // Endpos等价类的后缀链接和最大字符串长度
        int fa, len;
        // SAM的状态转移边
        int nxt[MAX_M];
    } T[(MAX_N << 1) + 50];
    // 节点数量计数、上一次扩展的节点位置
    int top = 1, lst = 1;
    // 插入一个后缀状态
    void insert(int x) {
        int p = lst, np = ++top;
        lst = top;
        T[np].len = T[p].len + 1;
        while (p && !T[p].nxt[x]) {
            T[p].nxt[x] = np;
            p = T[p].fa;
        }
        if (!p)
            T[np].fa = 1;
        else {
            int q = T[p].nxt[x];
            if (T[q].len == T[p].len + 1)
                T[np].fa = q;
            else {
                int nq = ++top;
                T[nq] = T[q];
                T[nq].len = T[p].len + 1;
                T[np].fa = T[q].fa = nq;
                while (p && T[p].nxt[x] == q) {
                    T[p].nxt[x] = nq;
                    p = T[p].fa;
                }
            }
        }
    }
    // 构造SAM
    void build(const char s[]) {
        for (int i = 0; s[i]; ++i)
            insert(s[i] - 'a');
    }
};

这是SAM的最基础的板子,但它却可以在每一步插入中完成构造Endpos等价类、更新Parent Tree和更新SAM的功能。

我们在构造SAM的时候直接调用SAM::build()函数,可以看到这个函数本质上就是按顺序把字符串的每个字符依次插入SAM,所以真正有用的部分应该是SAM::insert(),我们现在直接对SAM::insert()进行分析:

1. 新建节点

    // ...
    void insert(int x) {
        int p = lst, np = ++top;
        lst = top;
        T[np].len = T[p].len + 1;
    // ...

这段其实没什么好说的,p会指向上一次插入的节点,np是我们新建的节点,然后将lst指向我们新建的节点,因为在下一次插入时的p’应该指向np。

T[np].len设置为T[p].len + 1其实也不难理解,因为当一个字符串在末尾插入了一个新字符后,整个字符串会形成一个新的Endpos等价类,而这个等价类的长度就是上次插入的等价类长度加1。

2. 调整SAM转移路径

        // ...
        while (p && !T[p].nxt[x]) {
            T[p].nxt[x] = np;
            p = T[p].fa;
        }
        // ...

我们不断地从上一个插入的位置跳转后缀链接,寻找所有没有转移到x字符的位置,将它们的转移指针指向新节点np。

从上一个位置跳转后缀链接,如果你还记得我们对SAM的定义(不记得就点这里),就知道这实际上是在遍历上一次插入后整个SAM的终止节点,并检查其是否有到x的转移,如果没有我们就把它链接到新节点。这其实就是对旧的Endpos等价类进行扩展,所有旧终止节点都可以通过添加字符x来转移到新的状态np。

3. 调整唯一终止节点

        // ...
        if (!p)
            T[np].fa = 1;
        // ...

如果所有的旧终止节点都可以被遍历,最后回到了起始节点,那么说明所有的终止节点都不再是终止节点(因为他们可以转移到np),新的终止节点就只剩下了np,这时我们把np的后缀链接调整到起始节点,这样下一次遍历的时候只会遍历到np。

4. 调整新增终止节点

        // ...
        else {
            int q = T[p].nxt[x];
            if (T[q].len == T[p].len + 1)
                T[np].fa = q;
        // ...

如果有某个旧终止节点已经存在了一个字符x转移,那么说明这一个由字符x转移的节点q有成为新的终止节点的潜力。

这时我们检查q的len是否比其父节点p的len大1,即q的Endpos等价类是p的一个最大划分,那么就可以把np的后缀链接调调整到q上了,因为此时q也是一个合法的结束状态。

需要注意的是,在q成为终止节点后,原来p后缀链接上的部分终止节点就不再是终止节点了,新的终止节点遍历将经过q而走q的后缀链接,因为Endpos等价类的划分关系发生了改变。

5. 调整节点关系

            // ...
            else {
                int nq = ++top;
                T[nq] = T[q];
                T[nq].len = T[p].len + 1;
                T[np].fa = T[q].fa = nq;
                while (p && T[p].nxt[x] == q) {
                    T[p].nxt[x] = nq;
                    p = T[p].fa;
                }
            }
            // ...

如果q的Endpos等价类不是p的一个最大划分,那么我们需要新建一个中间节点了,让这个节点成为p的最大划分。

我们需要从q等价类继承一部分信息构造nq,首先就是令T[nq].len等于T[p].len+1,表明等价类nq是p的一个新划分,在那之前我们还把q的所有状态转移赋予了nq,因为此时我们本质上是让nq成为p的一个最大划分,从p到q再继续转移本质上与从p到nq再继续转移是一样的。

然后我们调整np和q的后缀链接为nq,对np来说,就相当于第(4)步,对于q来说,就相当于更新了等价类从属关系,它本身会成为nq的一个划分。

最后我们还是遍历p的后缀链接,把所有链接到q上的转移换成链接到nq上,本质上还是把q替换成nq操作。

构造SAM其实就是两步,新建节点+调整路径。

0x04 广义后缀自动机(GSAM)

广义后缀自动机GSAM(General Suffix Automaton)是SAM家族的另一大神器,它可以用来解决多字符串后缀自动机问题。

GSAM依赖于一棵Trie树,并在遍历Trie树的过程中建立一个后缀自动机。为此我们其实只需要对普通的SAM代码进行一些修改:

// 字符串长度
#define MAX_N 114514
// 字符集大小
#define MAX_M 26

// 广义后缀自动机结构
struct GSAM {
    struct Node {
        // Endpos等价类的后缀链接和最大字符串长度
        int fa, len;
        // SAM的状态转移边
        int nxt[MAX_M];
    } T[(MAX_N << 1) + 50];
    // 节点数量计数
    int top = 1;
    // 从给定的位置插入一个后缀状态
    int insert(int x, int lst) {
        // 特判
        if (T[lst].nxt[x]) {
            int p = lst, q = T[lst].nxt[x];
            if (T[q].len == T[p].len + 1)
                return q;
            int nq = ++top;
            T[nq] = T[q];
            T[nq].len = T[p].len + 1;
            T[q].fa = nq;
            while (p && T[p].nxt[x] == q) {
                T[p].nxt[x] = nq;
                p = T[p].fa;
            }
            return nq;
        }
        // 和SAM一样
        int p = lst, np = ++top;
        T[np].len = T[p].len + 1;
        while (p && !T[p].nxt[x]) {
            T[p].nxt[x] = np;
            p = T[p].fa;
        }
        if (!p)
            T[np].fa = 1;
        else {
            int q = T[p].nxt[x];
            if (T[q].len == T[p].len + 1)
                T[np].fa = q;
            else {
                int nq = ++top;
                T[nq] = T[q];
                T[nq].len = T[p].len + 1;
                T[np].fa = T[q].fa = nq;
                while (p && T[p].nxt[x] == q) {
                    T[p].nxt[x] = nq;
                    p = T[p].fa;
                }
            }
        }
        // 记得返回
        return np;
    }
};

主要修改部分就是GSAM::insert(),该函数每次会返回上一次输入字符的节点编号,同时也要求输入一个节点编号作为lst执行插入。

GSAM和SAM最大的不同其实就是开头的那一段:

        // ...
        if (T[lst].nxt[x]) {
            int p = lst, q = T[lst].nxt[x];
            if (T[q].len == T[p].len + 1)
                return q;
            int nq = ++top;
            T[nq] = T[q];
            T[nq].len = T[p].len + 1;
            T[q].fa = nq;
            while (p && T[p].nxt[x] == q) {
                T[p].nxt[x] = nq;
                p = T[p].fa;
            }
            return nq;
        }
        // ...

其实非常好理解,就相当于你要插入的位置本来就已经存在了一个转移,那么就可以如法炮制,用构造SAM时的第5步那样处理就行了,当然你还需要注意返回值是什么。

既然GSAM::insert()已经被修改了,那么构造方式当然也要变:

// 遍历Trie树
void dfs(int u, int lst) {
    // 将Trie节点u所代表的的字符插入到GSAM中
    lst = gsam.insert(s[u] - 'a', lst);
    // 遍历Trie子节点
    for (int i = 0; i < MAX_M; ++i)
        if (trie[u][i])
            dfs(trie[u][i], lst);
}

这样一来,我们的GSAM中就存储了整个Trie树的后缀信息,然后你就可以把GSAM当做普通的SAM来用了。

当然构造GSAM除了使用dfs以外,还可以使用bfs,只需要稍微改一改dfs代码就行了,此处不再给出。

除了这种Trie树和GSAM主结构分开的的形式,还有一种直接在Trie树上构造GSAM的形式,这种形式可以省去一个Trie的空间:

// 字符串长度
#define MAX_N 114514
// 字符集大小
#define MAX_M 26

// 广义后缀自动机结构
struct GSAM {
    struct Node {
        // Endpos等价类的后缀链接和最大字符串长度
        int fa, len;
        // SAM的状态转移边
        int nxt[MAX_M];
    } T[(MAX_N << 1) + 50];
    // 节点数量计数
    int top = 1;
    // 插入Trie树
    void insertTrie(const char s[]) {
        int j = 1;
        for (int i = 0, x; s[i]; ++i) {
            x = s[i] - 'a';
            if (!trie[j][x])
                trie[j][x] = ++top;
            j = trie[j][x];
        }
    }
    // 插入GSAM
    int insertGSAM(int x, int lst) {
        int p = lst, np = T[lst].nxt[x];
        T[np].len = T[p].len + 1;
        p = T[p].fa;
        while (p && !T[p].nxt[x]) {
            T[p].nxt[x] = np;
            p = T[p].fa;
        }
        if (!p)
            T[np].fa = 1;
        else {
            int q = T[p].nxt[x];
            if (T[q].len == T[p].len + 1)
                T[np].fa = q;
            else {
                int nq = ++top;
                T[nq] = T[q];
                T[nq].len = T[p].len + 1;
                T[np].fa = T[q].fa = nq;
                while (p && T[p].nxt[x] == q) {
                    T[p].nxt[x] = nq;
                    p = T[p].fa;
                }
            }
        }
        return np;
    }
    // 构造GSAM
    void build() {
        std::queue<std::pair<int, int>> que;
        for (int i = 0; i < MAX_M; ++i)
            if (trie[1][i])
                que.emplace(i, 1);
        while (!que.empty()) {
            auto tmp = que.front();
            que.pop();
            int lst = insertGSAM(tmp.first, tmp.second);
            for (int i = 0; i < MAX_M; ++i)
                if (T[lst].nxt[i])
                    que.emplace(i, lst);
        }
    }
};

首先是插入Trie树的GSAM::insertTrie(),相信大家都明白,然后我们看看经过了修改的GSAM::insertGSAM(),可以发现其实大部分和我们上面的第一份GSAM的GSAM::insert()是一样的,唯一不同点是这里:

    // ...
    int insertGSAM(int x, int lst) {
        int p = lst, np = T[lst].nxt[x];
        T[np].len = T[p].len + 1;
        p = T[p].fa;
    // ...

由于我们是直接在Trie树上建的GSAM,所以当我们在lst插入x节点时,实际上要调整的节点是T[lst].nxt[x],所以我们直接调整把这个节点当做普通SAM插入的节点即可,至于后面为什么还要p = T[p].fa,这也很显然,因为下面的while循环会判断一次T[p].nxt[x],如果不提前修改p的话,那循环就会直接退出,也就没起到遍历上一次插入的终止节点的作用了。

然后是构造GSAM的GSAM::build(),我们可以看到,其实这就是我们第一份GSAM构造代码的BFS版本,所以解释意义如上一样。

0x05 伪广义自动机

伪广义自动机PGSAM(Pseudo General Suffix Automaton)(没有这种缩写),是指用一些奇淫技巧使SAM能够拥有GSAM的功能,但是其构造并不符合标准GSAM的要求。

伪广义自动机可以使用如下两种构造方法:

  1. 将不同的字符串之间用一个特殊且唯一的符号隔开,连接成一个全新的字符串,然后用其来构造SAM
  2. 在插入一个字符串后,将SAM的lst重置为1

虽然这两种操作都很简单,但是他们就是可以得到正确的答案,所以被称为伪广义自动机

伪广义自动机是复杂度危险的,一般情况下尽量不要使用,除非遇到了某些要求苛刻的题目(如卡Trie树的空间),才使用伪广义自动机。

0x06 后缀自动机的应用

1. 检查一个字符串是否为子串

这个非常简单,因为SAM中存储了字符串所有的后缀信息,所以只需要在SAM上跑匹配,如果走到了一个不存在的节点,那么该字符串一定不是子串。

2. 计算一个字符串本质不同的子串数量

这个也很简单,因为SAM的每个节点存储一个Endpos等价类,每个Endpos等价类中的字符串长度是有序的,且各个Endpos等价类都是不同的,那么问题的答案就是所有Endpos等价类的字符串数量之和。

而在Parent Tree上,一个Endpos等价类A的大小是:$maxLen(A)-minLen(A)+1$,也就是:$maxLen(A)-maxLen(fa(A))$,其中fa(A)代表等价类A在Parent Tree上的父节点。

所以答案就是:$\sum(maxLen(i)-maxLen(fa(i)))$

例题:生成魔咒 - bzoj4516

3. 计算一个字符串本质不同的子串长度和

和上一题一模一样,只不过把计数变成了计算长度,那么一个Endpos等价类A的长度和就是:
$\frac{maxLen(A)\cdot(maxLen(A)+1)-maxLen(fa(A))\cdot(maxLen(fa(A))+1)}{2}$

总和就是:
$\sum\frac{maxLen(i)\cdot(maxLen(i)+1)-maxLen(fa(i))\cdot(maxLen(fa(i))+1)}{2}$

4. 字典序第k大子串

这个问题上本质上是求SAM上字典序第k大的路径,这就要求我们统计每个节点的路径总数,然后寻找第k大。

我们可以根据$maxLen$对每个节点进行一次拓扑排序,然后根据拓扑序倒推每个节点的路径数量。

一个节点的路径数量为:
$$sum[i]=1+\sum_{j\in V_i}sum[j]$$

其中$j$为$i$的子节点。

例题:SPOJ - SUBLEX

5. 最小循环移位

这题其实用最小表示法计算更快更方便
易知对于字符串$S$,新字符串$SS$显然包含了$S$所有的循环移位方案,那么我们只需要对$SS$构造SAM,然后贪心地在SAM上走最小的节点,直到走的长度为$|S|$为止。

6. 子串的出现次数

除非查询次数多且子串长度长,否则这题用KMP更好
设需要查询的子串为$P$,我们只需要在SAM上匹配这个子串,如果走到了不存在的节点,那么说明该子串不存在,否则我们可以到达一个节点,而这个节点的Endpos等价类大小就是$P$的出现次数。

7. 子串第一次出现的位置

不推荐理由同上,除非条件苛刻否则KMP走起
对于每个节点维护一个数组first[]表示这个Endpos等价类中最短串的首位置。

在SAM插入操作过程中,当新建节点np时,我们令first[np] = T[np].len - 1,当新建节点nq时,我们令first[nq] = first[q]

经过如上预处理操作后,对于子串$P$,我们在SAM上匹配这个串,直到在某个节点x上结束,查询的结果就是$first[x]-|P|+1$。

8. 子串所有的出现位置

不推荐理由同上,除非条件苛刻否则KMP走起
前面的操作与7中相同,但是我们在预处理的过程中还需要记录节点在Parent Tree上的子节点。

我们仍旧最后会在一个节点x处停下,并输出第一次出现的位置,但是接下来我们需要遍历x节点在Parent Tree上的子树,一旦找到了终止节点,那么我们还需要输出一次答案,这样我们才能得到所有出现的位置。

9. 两个字符串的最长公共子串

设两个字符串$S_1$、$S_2$,我们对$S_1$构造SAM,然后用$S_2$在SAM上进行匹配,我们需要维护两个变量$u$和$l$,分别代表当前节点编号和当前匹配长度。

一开始令u = 1, l = 0,然后扫描$S_2$,对于第$i$个字符$c$:

  1. 如果存在从$u$到$c$的转移,那么直接转移并使$l$增加1
  2. 如果不存在,那么我们就沿着后缀链接走,缩短匹配的长度,即:u = T[u].fa, l = T[u].len
  3. 如果此时$u$已经到达了起始状态1,那么令l = 0表示字符$c$根本没在$S_1$中出现过

我们不断扫描并执行以上三种动作,并不停更新记录$l$的最大值,直到扫描完成,这时候最大值就是两个字符串的最长公共子串长度。

如果你想得到最长公共子串,那么只需要在最大值更新的时候同时记录位置信息即可。

10. 多个字符串的最长公共子串

和求两个字符串的最长公共子串差不多,对第一个字符串建SAM,然后用其他字符串在上面匹配,但我们需要保存在每个节点$u$上所算得的$l$。

我们将每轮字符串匹配所算得的$l$保存在$tmp_u$中,在当前字符串都匹配完了之后,用$tmp_u$更新当前节点$u$的$l$最小值,记为$min_u$,最终的答案就是$\max\{min_u\}$。

但是在每次$tmp_u$更新之后,其实$tmp_{fa(u)}$也需要更新,因为父节点$fa(u)$本质上是$u$的后缀子串,当$u$有了更长的匹配,那么$fa(u)$的最长匹配应该从$u$那里继承,所以在每轮字符串匹配完成后,我们需要跑一边拓扑序,把所有节点的父节点长度$tmp_{fa(u)}$更新,然后再去更新$min_u$。

需要注意的是,我们需要将$min_u$初始化为$len_u$因为一个状态的最长公共子串不可能比它所代表的Endpos等价类最长串还要长。

如果还你不太懂,这是一份AC代码

0x07 最后的话

当你做多了SAM的题目之后,你会发现有个东西——拓扑排序是经常用到的。

SAM最后形成的图是一个DAG,所以一定存在这么一个拓扑序,而它能很好地反映各个节点之间的拓展关系。然后出题人就会在拓扑序的基础上套DP了。然后就是万物皆可DP。

当然SAM上的拓扑排序不需要像普通拓扑排序一样统计什么入度信息,而是直接对每个节点以len进行一次基数排序即可,因为我们保证了DAG上的父子节点之间的len值一定是有序的。

又因为拓扑序的存在,我们就可以把图上搜索统计的一些题目通过拓扑序改成线性统计了,这样极大地提高了计算的效率。

最后贡献一份SAM拓扑排序的代码:

    // ...
    // 基数排序用的桶、存储拓扑序的数组
    int bk[], tp[];
    void topology() {
        for (int i = 1; i <= top; ++i)
            ++bk[T[i].len];
        for (int i = 1; i <= top; ++i)
            bk[i] += bk[i - 1];
        for (int i = 1; i <= top; ++i)
            tp[bk[T[i].len]--] = i;
    }
    // ...

0x08 题单

题目难度备注
生成魔咒 - bzoj45161SAM模板题,本质不同子串数量
SPOJ - NSUBSTR1SAM模板题,节点路径总数问题
SPOJ - LCS2SAM模板题,最长公共子串长度
SPOJ - SUBLEX2SAM模板题,第k大子串
诸神眷顾的幻想乡 - bzoj39262GSAM模板题,本质不同子串数量
差异 - bzoj32383SAM+树形DP
Good Article Good sentence - HDU44163伪广义自动机,本质不同子串数量
SPOJ - LCS23SAM多字符串最长公共子串
世界线 - bzoj28944GSAM第k大子串
str2int - HDU44364GSAM上拓扑排序构造不同子串进行计数
找相同字符 - bzoj45665SAM+DP

0x09 广告

万年未更新的博客:https://rainiar.top

0xA0 鸣谢

史上最通俗的后缀自动机详解 - KesdiaelKen 的博客 - 洛谷博客
后缀自动机 (SAM) - OI Wiki
广义后缀自动机 - OI Wiki

标签: 算法, 字符串, SAM, GSAM

文档最后编辑于04月28日

评论

让我也说点啥