看完这篇，你一定会感慨“后缀自动机，就这？”

ACM算法日常

发布于 2021-09-07 14:53:08

9700

发布于 2021-09-07 14:53:08

文章被收录于专栏：ACM算法日常

后缀自动机 (suffix automaton, SAM) 是一个能解决许多字符串相关问题的有力的数据结构。

字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是， SAM 将所有的这些信息以高度压缩的形式储存。对于一个长度为

字符串，它的空间复杂度仅为

O(n)

此外，构造 SAM 的时间复杂度仅为

O(n)

这里我们将字符集的大小

\|\sum \|

看作常数，否则时间复杂度和空间复杂度均为

O(nlog\|\sum \|)

定义

字符串

的 SAM 是一个接受

的所有后缀的最小 DFA 确定性有限自动机或确定性有限状态自动机）。

具体来说：

SAM 是 DAG 。结点被称作状态，边被称做转移。
图有一个源点

t_0

，称作初始状态，其它各结点均可从

t_0

出发到达。

每个转移都标有一些字母。从一个结点出发的所有转移均不同。
存在一个或多个终止状态。如果我们从初始状态

t_0

出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串

的一个后缀。的每个后缀均可用一条从

t_0

到某个终止状态的路径构成。

在所有满足上述条件的自动机中， SAM 的结点数是最少的。

重要的性质

SAM 最重要的性质就是，它包含了字符串

的所有子串信息。任意从初始状态

t_0

开始的路径，如果我们将转移路径上的标号写下来，都会形成

的一个子串。也就是说子串对应一条路径（从

t_0

出发）。

到达某个状态的路径可能不止一条。

构造 SAM

模版

struct sam
{
    const int M=N<<1;
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1;
    void init(){memset(t,0,(sz+10)*sizeof t[0]);sz=2;last=1;}
    void ins(int ch)
    {
        int p=last,np=last=sz++;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
    int c[M]={1},a[M];
    void rsort()
    {
        for (int i=1;i<sz;i++) c[i]=0;
        for (int i=1;i<sz;i++) c[len[i]]++;
        for (int i=1;i<sz;i++) c[i]+=c[i-1];
        for (int i=1;i<sz;i++) a[--c[len[i]]]=i;
    }
}

例题

这一次，我们就看一道简单的例题，更加困难的题目，我们会在下一周讲解。

Hihocoder1445 重复旋律5

显然对于每一个状态

，它所代表的不同子串个数是

len[v]-len[link[v]]

。

所以整个字符串中不同子串的个数就是

\sum_{i=0}^{sz} (len[v]-len[link[v]])

。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define N 2000010
const int M=N<<1;

struct sam
{
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1;
    void init(){memset(t,0,(sz+10)*sizeof t[0]);sz=2;last=1;}
    void ins(int ch)
    {
        int p=last,np=last=sz++;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
}a;

int n;
char s[N];

int main()
{
    scanf("%s",s);
    n=strlen(s);
    a.init();
    for (int i=0;i<n;i++)
        a.ins(s[i]-'a');
    LL ans=0;
    for (int i=2;i<a.sz;i++)
        ans+=(LL)(a.len[i]-a.len[a.fa[i]]);
    cout<<ans<<endl;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

文件存储

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

文件存储

登录后参与评论

0 条评论

热度