柒葉灬 的博客

柒葉灬 的博客

后缀自动机(个人笔记)

posted on 2019-04-18 20:44:21 | under 专题总结 |

后缀自动机


具体原理就不多叙述了,网上已经很清楚了。


模板

struct node{
    int son[26],len,fa;
    void clear(){
        memset(son,0,sizeof(son));
        len=fa=0;
    }
}t[maxn<<1];

void extend(int c){
    int p=last,np=last=++tot;
    t[np].clear();
    t[np].len=t[p].len+1;
    while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].fa;
    if(!p)t[np].fa=1;
    else {
        int q=t[p].son[c];
        if(t[q].len==t[p].len+1)t[np].fa=q;
        else {
            int nq=++tot;
            t[nq]=t[q];t[nq].len=t[p].len+1;
            t[q].fa=t[np].fa=nq;
            while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].fa;
        }
    }
}

一句话题解系列(雾):

专题A

每一次询问的时候重新在 $[l,r]$ 区间内建 $SAM$

看似很暴力,实则复杂度是对的,

记住SAM建立的复杂度是 $O(n)$ 的。


专题B

题意:有多少个是字符串A的子串,但不是字符串Bi的子串。

输入Bi串的时候跑一遍自动机,标记每个点可延伸最长的子串

合法串的个数就是 $max(0,t[x].len-max(Max[x],t[f].len))$

拓扑排序把最大值贡献给父亲,


专题C

题意:查找两个串的最长公共子串

对着一个建SAM,然后另一个串跑自动机,

如果 $trans$ 指向的点为0时,跳slink数组,

然后更新当前匹配长度, $len=t[x].len$

可以发现,这跳slink的操作就像跳fail数组一样,

答案就是len的最大值。

(不知道为什么强行把 $last=1$ 会对)


专题D

题意:给n个串,输出询问串有多少个与其有相同endpos的串

每两个串之间插入一个从未出现过的字符,

求出每个节点的最小len值,防止有特殊字符串被计入答案。


专题E

题意:求有多少个子串出现至少两次,且两次不重叠。

算每一个节点endpos的最大值和最小值,

计算每一个节点贡献子串就行了。

专题F

题意:求有多少个子串出现恰好 $K$ 次。(水题)

每个节点出现个数就是endpos的个数,

拓扑排序收集个数即可

专题G

题意:有多少个子串出现至少 $K$ 次,有加字符操作

离线,建一个完整的SAM,

算每一个节点第K个endpos的位置,

需要用到线段树合并

每一次计算之后合并到父亲即可,不需要可持久化。


专题H

题意:详见后缀数组专题的翻译(233)

对串反向建SAM,维护每一个节点最小的endpos

记录下每一个后缀的对应的节点,

倍增跳fa,找到第一个mn小于当前x的节点,len就是最大lcp


专题I

(难题)

题意:从A中取一个子串x,B中取一个子串y,问x+y可以形成多少不同的新串(x,y均可以为空串)

这题最麻烦的就是会有重复的,即使 $x!=x',y!=y'$ ,也有可能出现 $x+y==x'+y'$

为了防止这种情况出现,可以使取出的x尽可能长,

即,x加上y的第一个字符不属于A的子串

最终得到:扫一遍A的SAM,若trans(x,i)==NULL,

则判断B当中以i为开始有多少不同子串即可,

最后在特殊处理一下空串的情况就能A了。


专题J

(好题)

题意:给一个目标串。每次有两种操作:

1.在当前串后面加字符,代价为对应字符的成本cost[i]

2.选则一段长度len的子串,复制到后面,花费A*len+2*B

初始为空串,问达到目标串的最小代价。

这题显然是需要dp的,每次转移时重点就在操作2上,

可以发现,只要知道最远能从哪里转移就行了,

区间求min,用树状数组维护最小值,倍增维护最远点。

补充:

这题可以在线建立着一个SAM,

使得这个SAM的长度就是上面提到的需要维护的最小值 $j$ ,

如果不能匹配了就 $extend(str[++j])$

直到能够匹配或者 $i==j$

复杂度从 $O(nlogn)$ 到 $O(n)$