算法总结:广义后缀自动机

简介

广义后缀自动机,说白了就是把若干个字符串建进同一个SAM里。

广义SAM中,一个状态的right集合表示:这个状态表示的串在所有字符串里的所有出现位置。只有所有出现位置均相同的串才会被合并到同一个状态。

当然也可以分开统计某个状态在每个字符串里分别出现过几次。

建法:在新插入一个字符串时,令$last=1$。另外还有一些细节,见代码。

例题:

bzoj4566 [Haoi2016]找相同字符

bzoj3926 [Zjoi2015]诸神眷顾的幻想乡

代码

void Extend(char c) {
    int x = c - 'a', p = last, tmp = ch[p][x];
    if (tmp && mx[tmp] == mx[p] + 1) { cnt[last = tmp]++; return; }  // (1)
    int np = last = ++top; mx[np] = mx[p] + 1; cnt[np]++;
    for (; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
    if (!p) { fa[np] = 1; return; }
    int q = ch[p][x];
    if (mx[q] == mx[p] + 1) { fa[np] = q; return; }
    int nq = (mx[p]+1 == mx[np] ? np : ++top);  // (2)
    mx[nq] = mx[p] + 1;
    fa[nq] = fa[q]; fa[q] = nq;
    if (nq != np) fa[np] = nq;  // (3)
    memcpy(ch[nq], ch[q], sizeof(ch[nq]));
    for (; ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
}

注意事项

其实接下来才是这篇文章的主要内容。

注意上面代码的(1)(2)(3)三行,这三行是广义SAM与普通SAM代码的区别之处。

(1)很好理解,如果当前要新增的状态之前已经建过了,就不必再建。

不过,如果只写(1)不写(2)(3),就会经常出现一些莫名其妙的错误。

错误的原因是,在广义后缀自动机中,会出现父亲与儿子的$mx$相等的情况。

众所周知,SAM的题目中经常需要把儿子的信息统计给父亲。代码实现方法有两种:直接把parent树建出来然后dfs,或者求出拓扑序后按顺序访问。

用第一种方法是不会出错的,但代码繁琐。对于第二种方法,需要对$mx$进行基数排序,但若父子$mx$相等,并且父子的编号大小关系是不确定的,那么就无法用基排确定拓扑序。

显然,$mx(fa(u))=mx(u)$的节点$u$是没用的,因为$min(u)=mx(fa(u))+1>mx(u)$。所以我们只需要把这样的节点删掉,或者说不建出来即可。

考虑一下为什么会出现这样的节点。令$(id,pos)$表示第$id$个字符串的第$pos$个位置。观察到我们每次新插入一个字符(假设插入第$i$个字符串的第$j$个字符)的时候,会新建一个状态$np$。此时$np$的right集合为$\{(i,j)\}$,并且无论如何它一定会被加入SAM中。

但如果此时不存在right集合为$\{(i,j)\}$的节点呢?也就是说,第$i$个字符串的所有以位置$j$结尾的子串,在前$i-1$个串中都出现过了。那么这个$np$就是一个无意义的节点,考虑如何将它删除。

为了删除无意义$np$,我们需要找到它的父子关系。为此,先跟着代码走一遍:

由于以$(i,j)$结尾的所有串都出现过了,则显然$ch(last,x)\not=0$(这种情况只有在多串SAM中才会出现),那么$p=last,q=ch(p,x)$。由于(1)的特判,$mx(q)\not=mx(p)+1$,所以需要新建节点$nq$。

按照单串SAM的建法,$mx(nq)=mx(p)+1$。此时因为$p=last$,所以$mx(np)=mx(last)+1=mx(p)+1=mx(nq)$。并且接下来我们将会令$fa[np]=nq$,这就是无意义节点的来源。

所以,解决方法就很显然了:若$mx(p)+1=mx(np)$,即$mx(nq)=mx(np)$,则删除$np$。为了节省空间,可以把$np$的空间拿给$nq$用。这就是代码(2)(3)处的原理。

另外,要记得把原本统计在$np$上的信息移到$nq$上,比如上面代码中的$cnt$,即right集合大小。不过因为我直接让$nq$用了$np$的编号,所以就不需要再$cnt(nq)++$了。

写完(2)(3)后,就可以肆无忌惮地基排了。



转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论