@xiaoziyao 2021-01-31T05:48:41.000000Z 字数 7111 阅读 2648

后缀自动机（SAM）/广义后缀自动机（广义SAM）应用与做题记录

字符串 学习笔记

做了一些SAM和广义SAM的题，总结出一些套路，把它们记下来以供参考。

SAM板子：

int extend(int last,int x){
    int now=++tot,pos=last,tmp,cln;
    len[now]=len[pos]+1;
    tag[now]=1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    len[cln]=len[pos]+1;
    for(int i=1;i<=26;i++)
        nxt[cln][i]=nxt[tmp][i];
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}

cin>>s;
n=s.size(),s=" "+s;
last=++tot;
for(i=1;i<=n;i++)
    last=extend(s[i]-96);

广义SAM板子：

int extend(int last,int x){
    if(nxt[last][x]){
        int pos=last,tmp=nxt[pos][x],cln;
        if(len[tmp]==len[pos]+1)
            return tmp;
        cln=++tot;
        for(int i=1;i<=26;i++)
            nxt[cln][i]=nxt[tmp][i];
        len[cln]=len[pos]+1;
        link[cln]=link[tmp],link[tmp]=cln;
        while(pos!=0&&nxt[pos][x]==tmp)
            nxt[pos][x]=cln,pos=link[pos];
        return cln;
    }
    int now=++tot,pos=last,tmp,cln;
    len[now]=len[pos]+1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    len[cln]=len[pos]+1;
    for(int i=1;i<=26;i++)
        nxt[cln][i]=nxt[tmp][i];
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}

1.处理各种字符串信息

SAM可以很简单地处理各种关于子串长度，子串出现次数等信息。

子串出现次数：对于某个状态，它的出现次数可以在Parent Tree上记一下数（具体地，对于每一次 $extend$ 的 $now$ ，记录 $tag_{now}=1$ ，然后在Parent Tree上求这个子树的 $tag$ 之和）

void dfs(int x){
    size[x]=tag[x];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dfs(y);
        size[x]+=size[y];
    }
}

（其中 $size$ 就是出现次数）

子串长度：某个状态 $x$ 的包含的所有子串的长度恰好为区间 $[len_{link_x}+1,len_x]$ ，且不重不漏。

似乎没有什么要放的代码，凑个数QAQ

子串长度出现次数：对于某个状态，区间修改一下子串长度区间，一般可以差分做。

cnt[len[link[x]]+1]++,cnt[len[x]+1]--;
for(i=1;i<=n;i++)
    cnt[i]+=cnt[i-1];

P3804 【模板】后缀自动机 (SAM)：求所有出现次数不为 $1$ 的子串出现次数乘该子串长度的最大值，直接统计就可以了。
P5341 [TJOI2019]甲苯先生和大中锋的字符串：求恰好出现 $k$ 次的子串中出现次数最多的长度，在Parent Tree上求一下各种信息，恰好出现 $k$ 次的状态都区间修改一下长度的出现次数，可以差分一下，然后前缀和统计答案。
CF802I Fake News (hard)：求所有子串的出现次数平方和，直接统计就可以了。
CF123D String：求所有子串的出现次数乘(出现次数 $+1$ )之和，直接统计就可以了。
SP8222 NSUBSTR - Substrings：给定长度为 $n$ 的串 $s$ ，求长度为 $1\cdots n$ 的子串在 $s$ 中最大出现次数。
CF316G3 Good Substrings：直接建广义SAM暴力算就好了

2.求本质不同子串个数

方法 $1$ ：Parent Tree上计一下数。
方法 $2$ ：DAWG上计算路径个数。
方法 $3$ ：（在线）每一次加入一个串都将新建的结点包含的子串个数统计到答案中（即 $len_{now}-len_{link_{now}}$ ）。
应该按不同情况选择不同的方法。

方法 $1$ ：

void dfs(int x){
    size[x]=len[x]-len[link[x]];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dfs(y);
        size[x]+=size[y];
    }
}

方法 $2$ ：

void dfs(int x){
    if(ans[x])
        return ;
    ans[x]=1;
    for(int i=1;i<=26;i++)
        if(nxt[x][i]){
            dfs(nxt[x][i]);
            ans[x]+=ans[nxt[x][i]];
        }
}

方法 $3$ ：

for(i=1;i<=n;i++){
    last=extend(last,s[i]);
    ans+=(len[last]-len[link[last]]);
}

SP694 DISUBSTR - Distinct Substrings求本质不同子串个数。
SP705 SUBST1 - New Distinct ：求本质不同子串个数，是上一题加强版。
P2408 不同子串个数：求本质不同子串个数。
P4070 [SDOI2016]生成魔咒：求本质不同子串个数，离散化+map优化。
SP32951 ADASTRNG - Ada and Substring：求某个字母开头本质不同子串个数。
#6071. 「2017 山东一轮集训 Day5」字符串：求多个串可空子串拼接后不同子串个数，对每个串建SAM，然后用子序列自动机把DAWG拼接起来，形成的新DAG有个美妙的性质：它上面的路径对应着所有新字符串的子串。这样，我们就只需要在上面计算路径数量就可以了。
P3181 [HAOI2016]找相同字符：求两个字符串中各取出一个子串使得这两个子串相同的方案数。直接建出一个串的SAM，跑dfs求出出现次数，然后跑个匹配就好了。
P6139 【模板】广义后缀自动机（广义 SAM）：求多串本质不同子串，建广义SAM后直接算
CF653F Paper task：求本质不同括号子串数量，用一个数据结构随便维护一下，用SAM判断本质不同就好了。

3.匹配子串/匹配循环同构

我们要在 $s$ 上匹配一个串，可以怎么做呢？

可以考虑不断让这个串进行两个操作：向前增加字符来进行匹配，将无法继续匹配的字符丢弃（以匹配后面的字符）。

我们在学习笔记辨析过Parent Tree和DAWG的差异与联系，在这里派上了用场：

如何在后面增加字符：跳一个为这个字符的DAWG边，一定让你恰好增加了一个字符。

如何在前面丢弃字符：每一次丢弃字符都暴力跳后缀link，直到到根结点或者存在当前匹配字符的DAWG边。由后缀link的定义可以知道跳后缀link是让你的 $endpos$ 发生改变的最小代价（即存在机会让你继续匹配），因此如果可以继续匹配，暴力跳后缀link一定可以跳到能匹配的状态。

因为每个状态最多遍历一遍，所以复杂度是 $O(n)$ 的。

int now=1,l=0;
for(i=1;i<=n;i++){
    while(now!=0&&nxt[now][s[i]]==0)
        now=link[now],l=len[now];
    if(nxt[now][s[i]])
        now=nxt[now][s[i]],l++;
    ......
}

循环同构： $s$ 的循环同构包括 $s_1\cdots s_n$ ， $s_2\cdots s_ns_1$ ， $s_3\cdots s_n s_1 s_2$ ， $\cdots$ ， $s_ns_1\cdots s_{n-1}$ （比如说， $aab$ 的循环同构有 $aab$ ， $baa$ ， $aba$ ）。

循环同构的匹配和普通串的匹配差不多，你只需要破环为链就可以了。（不过有一点要注意，如果匹配的长度大于该字符串的长度，那么需要强制失配）

破环为链就不需要代码了吧QAQ

CF235C Cyclical Quest：给定 $s$ 和若干个询问串 $t$ ，求每个 $t$ 的所有本质不同循环同构在 $s$ 的出现次数之和，循环同构破环为链就好了，到了长度需要强制失配，本质不同只需要打个标记就可以了。

P3763 [TJOI2017]DNA：直接在DAWG上跑dfs就好了。

4.最小表示法

最小表示法：求字符串字典序最小的循环同构

很简单，只需要倍长一下（因为要破环为链），建好SAM，然后在DAWG上贪心走字典序更小的边就可以了（也可以用 $map$ 记 $nxt$ ，然后用 $begin()$ 跳，这样快一些，而且在字符集过大之时有很好的优化作用）。

放的是第二种做法。

int now=1;
for(int i=1;i<=n;i++){
    int x=nxt[now].begin()->first;
    printf("%d ",x);
    i=nxt[i][x];
}

P1368 工艺 /【模板】最小表示法：板子题

5.求 $k$ 大子串

本质不同 $k$ 大子串：首先每个点点权为 $1$ ，然后在DAWG上计数，得到每个状态能达到的状态点权之和。搜索的时候判断一下，如果 $k$ 大于点权之和，我们就不走这个状态，然后把 $k$ 减一下，否则就走这个状态（因为这个状态能到达的串数量大于等于 $k$ ，那么第 $k$ 大一定包含在里面）。
位置不同 $k$ 大子串：在Parent Tree上求出每个状态出现次数，作为点权，转化为上面的情况。

本质不同 $k$ 小子串：

void getcnt(int x){
    if(cnt[x])
        return ;
    cnt[x]=x==1? 0:1;
    for(int i=1;i<=26;i++){
        int y=nxt[x][i];
        if(y==0)
            continue;
        getcnt(y);
        cnt[x]+=cnt[y];
    }
}
void query(int x,int k){
    if(k<=0)
        return ;
    for(int i=1;i<=26;i++){
        int y=nxt[x][i];
        if(y==0)
            continue;
        if(k>cnt[y]){
            k-=cnt[y];
            continue;
        }
        printf("%c",i+96);
        query(y,k-1);
        return ;
    }
}

位置不同 $k$ 小子串：

void getsize(int x){
    size[x]=tag[x];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        getsize(y);
        size[x]+=size[y];
    }
}
void getcnt(int x){
    if(cnt[x])
        return ;
    cnt[x]=x==1? 0:size[x];
    for(int i=1;i<=26;i++){
        int y=nxt[x][i];
        if(y==0)
            continue;
        getcnt(y);
        cnt[x]+=cnt[y];
    }
}
void query(int x,int k){
    if(k<=0)
        return ;
    for(int i=1;i<=26;i++){
        int y=nxt[x][i];
        if(y==0)
            continue;
        if(k>cnt[y]){
            k-=cnt[y];
            continue;
        }
        printf("%c",i+96);
        query(y,k-size[y]);
        return ;
    }
}

P3975 [TJOI2015]弦论：求本质不同/位置不同的 $k$ 小子串
SP7258 SUBLEX - Lexicographical Substring Search：求本质不同 $k$ 小子串

6.求公共串

我们定义 $end_{x,y}$ 代表状态 $x$ 是否在串 $y$ 中出现，这样我们每一次插入可以记录 $end$ 数组。然后在Parent Tree上合并一下，可以用 $bitset$ 优化到 $O(\frac{nm}{\omega})$ （ $n$ 为SAM状态数， $m$ 为串数），实际上也可以用线段树合并（见下面的"维护 $endpos$ "）。

bitset<maxn>end[maxn];
int extend(int last,int x){
    ......
    end[now][t]=1;
    ......
}
void dfs(int x){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dfs(y);
        end[x]|=end[y];
    }
    for(int i=1;i<=n;i++)
        if(end[x][i]==0)
            return ;
    ans=max(ans,len[x]);
}

SP1811 LCS - Longest Common Substring：求两串公共串，也可以用第二个串在第一个串上跑匹配。
SP1812 LCS2 - Longest Common Substring II：求多串公共串
SP10570 LONGCS - Longest Common Substring：多组数据，求多串公共串
P5546 [POI2000]公共串：求多串公共串
P2463 [SDOI2008]Sandy的卡片：求所有串的相同段（其中相同段的定义为这一段统一加上某个数就会变成另一端），差分一下就是求公共串的裸题

7.求后缀的 $lcp$ /前缀的 $lcs$

$lcp$ ，即 $Longest\ Common\ Prefix$ ，最长公共前缀； $lcs$ ，即 $Longest\ Common\ Suffix$ ，最长公共后缀。

有一个性质，反串SAM的Parent Tree是正串的后缀树，然后我们就可以利用SAM建后缀树了。

把串反过来建SAM不需要看了吧QAQ

然后还有一个性质，两个串的 $lcs$ 是它们在后缀树上对应的结点的 $lca$ （很显然，感性理解一下就好了），这样我们就可以用SAM求一些神奇的操作了。

LCA难道要看？

有时候会和虚树dp搭配在一起，SAM（细节少，不直观）+虚树dp（细节多，直观）=SAM上虚树dp（细节多，不直观）QAQ。

$lca$ 的 $\log$ 有时候会被卡，需要用ST表优化到 $O(1)$ 。

P4248 [AHOI2013]差异：求后缀的lcp，SAM辅助建后缀树，也可以考虑式子的意义，然后用点分治的思想给路径计数。
P1117 [NOI2016]优秀的拆分：SAM+部分结论+插点统计贡献（调和级数）
CF1073G Yet Another LCP Problem：SAM上虚树dp求 $lcp$ 。
SP687 REPEATS - Repeats：论文题。

8.维护 $endpos$

有些题目需要求SAM中 $endpos$ ，我们可以用几种方法来维护。（推荐使用方法 $3$ ，偷懒可以用方法 $2$ ，但不保证不会TLE）

方法 $1$ ：直接用二维数组 $endpos_{i,j}$ 表示状态 $i$ 的 $endpos$ 是否包括 $j$ ，在 $Parent Tree$ 上暴力合并，复杂度为 $O(n^2)$ 。
方法 $2$ ：用 $bitset$ 记录 $endpos$ ，然后在Parent Tree上合并 $endpos$ 就可以了，好写，复杂度优化为 $O(\frac{n^2}{\omega})$ 。
方法 $3$ ：用动态开点线段树记录每一个串的 $endpos$ ，然后再 $Parent Tree$ 上跑线段树合并（具体地，就是把每个位置 $i$ 都记录一个根结点 $rt_i$ ，以这个根结点建立动态开点线段树，修改直接单点修改结束的位置），复杂度为 $O(n\log n)$ ，缺点是炸空间。

注：SAM上线段树合并，经常和树上倍增搭配在一起，就是屑上加屑。

CF1037H Security：给定 $s$ ， $m$ 组询问，每组询问给定 $l,r,t$ ，求字典序最小的 $s'$ 满足 $s'$ 是 $s$ 的子串且 $s'$ 的字典序大于 $t$ （即求 $s_{l\cdots r}$ 内 $t$ 的前缀），我们可以用线段树合并维护出 $endpos$ 等价类，然后寻找替代 $t$ 每个字符的最小代价。具体地，我们边执行子串匹配（注意，这里的匹配不可以丢弃前面的字符，如果无法匹配下去就直接退出匹配），边从 $t_i$ 后面的字符到 $z$ 字符不断找，如果后面接上这个字符还在存在 $endpos$ 在限定的区间 $[l+len,r]$ 内（其中 $len$ 为已匹配的长度），那么这个字符是最小的能代替当前字符的字符。直到我们匹配完整个串，我们就贪心从后往前扫，扫到第一个可以替代的字符进行替代，然后输出。（有一个细节，匹配的长度需要到 $t$ 的长度 $+1$ ，比如说 $s=aaaaa,t=a,l=1,r=3$ ，此时答案为 $aa$ ）
P4094 [HEOI2016/TJOI2016]字符串：SAM+线段树合并+二分答案
CF666E Forensic Examination，广义SAM+线段树合并+子串匹配+树上倍增
P4770 [NOI2018] 你的名字：SAM+线段树合并+子串匹配
P5161 WD与数列：SAM+线段树合并+分类讨论

后缀自动机（SAM）/广义后缀自动机（广义SAM）应用与做题记录

1.处理各种字符串信息

2.求本质不同子串个数

3.匹配子串/匹配循环同构

4.最小表示法

5.求k大子串

6.求公共串

7.求后缀的lcp/前缀的lcs

8.维护endpos

参考文献

内容目录

5.求 $k$ 大子串

7.求后缀的 $lcp$ /前缀的 $lcs$

8.维护 $endpos$