后缀自动机(SAM)——黑盒使用方案

首先讲下后缀自动机吧，会写一下部分必要的原理，其他的原理不做解释。代码未讲解的部分希望能当做黑盒来使用（既不了解具体原理但知道其性质以及如何使用）。
我实在是佩服发明出AC自动机，回文自动机，后缀自动机这人

前置知识：AC自动机中的Fail树(了解)，字典树(熟练)，kmp(掌握)，后缀数组(了解）

什么是后缀自动机呢。

我们来看这样一个问题：我们要求把一个字符串S的所有后缀都插入到一个tire树中，这样的操作显然是n²的，但是实际在构造的过程中发现，只要能够重复利用某些节点，并且增加一些边，就能够在线性的级别做到构造出能够包含字符串s所有后缀信息的一个特殊的tire树。
之所以说是特殊的tire树，是因为这课树既包含了tire数也包含了fail树。

下面看一个举例。

例如：aababa的后缀自动机就像下面一样，黑色的线是tire树的，蓝色的是fail树的（文字没用）

这张图仅仅是让你了解一下后缀自动机的复杂结构。
至于这个DAG图怎么看呢，是这样的：从首节点出发，沿着任意一条路径走（你给我走黑色！），走到某个节点停下，路径就构成了一个子串。

后缀自动机都有什么性质

重要内容：right集，fail树，len数组，节点所代表串的长度连续性，节点之间绝对不相交
写代码之前先了解思想。

right集：

我们设字符串aababa为s。s的子串可能会重复出现，比如ba就出现了两次，一次是右端为4，一次是右端为6。我们设ba的right集就是｛4，6｝

再来看aba，aba的right显然也能求出是｛4，6｝，这里发现aba和ba的right集重合，更能发现一条新的性质：子串s1和s2的right相等时，较短者为较长者的后缀。

fail树：

我们忽略fail的具体建树过程，重点放在fail和连续性的关系上。

首先，观察下图，我们说蓝色边是fail。
我们对于fail树做如下约定

---

1.设fail[x]指向的节点为s，s节点代表的字符串拥有和x节点代表的字符串最长的公共后缀
2.设s节点代表的字符串当中长度最大的字符串的长度为len1，x节点代表的字符串中长度最短的字符串的长度为len2，必然有len1+1=len2

---

举例：节点8代表aababa，baba，ababa（长度4-6），节点9代表ba和aba（长度2-3）。

len数组：len[x]意义为：节点x所代表的字符串中最长的哪一个。
提问：x节点代表的最短的是什么呢？
答：len[fail[x]]+1；

节点所代表串的长度连续性

对于节点8，len[8]=6，len[fail[8]]+1=4.那么节点8一定一定能代表长度为4 5 6三个长度的子串。

节点之间绝对不相交
就是节点x代表的子串和节点y代表的子串绝对没有重合的。

怎么用代码构建自动机？

先放出代码
妈呀不想讲了qwq。
注意，构建的时候tire树在代码里的节点是红色的这个哦。

注释说明了代码的使用。

#include
using namespace std;
#define int long long
const int N=2000010;
char s[N];
string t;
int n,m,ans=0;
unordered_map<int,int>mp;

struct SuffixAutoMaton
{
    vector<int>right[N<<1];
    int tire[N<<1][26]/*如果确定了只有小写字母再用26吧,这tire树*/;
    int fail[N<<1],len[N<<1]/*fail数组，len和上方说的一样*/;
    int size[N<<1];/*在build函数的第五个for循环执行完之后得到的size[i]代表了节点i所代表的的right集合大小，也就可以说是节点i代表了几个子串*/
    int last,tot,k[N<<1],c[N<<1];/*用于在构建树的时候使用*/
    void init()
    {
        last=tot=1;memset(tire[1],0,sizeof tire[1]);//初始化没什么好说的吧，注意last和tot从1开始
    }
    void ins(int c,int pos)//传入当前插入的第i个字符，和i
    {
        int p=last;//上一个构建的节点是last，现在让p暂存last
        int np=++tot;//现在要构建的节点
        last=np;//更新last，你也可以把这一步放在后面
        len[np]=len[p]+1;//自然现在新构建的节点的最长长度是上一个节点的最长长度+1
        memset(tire[tot],0,sizeof tire[tot]);//初始化这一层的tire数
        for(;p&&!tire[p][c];p=fail[p])//构建tire树
            tire[p][c]=np;
        if(!p)//构建fail树的第一种情况，
            fail[np]=1;
        else//第二种
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else//第三种
            {
                int nq=++tot;//nq，我们在第三种情况下和第二种情况发生了本质的变化，我们再也不能通过现存节点来找到符合约定的fail节点，只能自己生成一个。第三种情况内部显然可以对nq的信息加以统计
                len[nq]=len[p]+1;
                memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        size[np]=1;
        right[np].push_back(pos);//把right集求出
    }
    void build(int n)
    {
        init();
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);//插入节点
        for(int i=1;i<=tot;i++) c[len[i]]++;//下面三个是排序，不动
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;

        for(int i=tot;i;i--)//这一步获取right集合right集大小，
        {
            int now=k[i];
            size[fail[now]]+=size[now];//求出了节点i的right集合大小
             for(auto j:right[now])
                right[fail[now]].push_back(j);//求出了right集
            //这下就可以根据节点+right集+size数组构建出子串的原有面貌。
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    sam.build(n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

接下来看两道模板题。

P2408 不同子串个数

给定一个字符串s，问字符串s能产生的所有不同子串的个数

思路：根据len数组和不重合性求解

#include
using namespace std;
#define int long long
const int N=2000010;
char s[N];
string t;
int n,m,ans=0;
unordered_map<int,int>mp;

struct SuffixAutoMaton
{
    //vectorright[N<<1];
    int tire[N<<1][26]/*如果确定了只有小写字母再用26吧*/,fail[N<<1],len[N<<1],size[N<<1],k[N<<1],c[N<<1];
    int last,tot;
    void init()
    {
        last=tot=1;memset(tire[1],0,sizeof tire[1]);
    }
    void ins(int c,int pos)
    {
        int p=last;
        int np=++tot;
        last=np;
        len[np]=len[p]+1;
        memset(tire[tot],0,sizeof tire[tot]);
        for(;p&&!tire[p][c];p=fail[p])
            tire[p][c]=np;
        if(!p)
            fail[np]=1;
        else
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else
            {
                int nq=++tot;
                len[nq]=len[p]+1;
                memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        size[np]=1;
        ans+=len[np]-len[fail[np]];
       // right[np].push_back(pos);
    }
    void build(int n)
    {
        init();
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);
        for(int i=1;i<=tot;i++) c[len[i]]++;
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;

        for(int i=tot;i;i--){
            int now=k[i];
            size[fail[now]]+=size[now];//求出了节点i的right集合大小
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    cin>>(s+1);
    sam.build(n);
    cout<<ans<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

P3804 【模板】后缀自动机 (SAM)

求：至少出现两次的子串*子串长度的最大值。

思路：子串长度：len，子串出现次数:right大小也就是size大小。

#include
using namespace std;
#define int long long
const int N=2000010;
char s[N];
string t;
int n,m;
unordered_map<int,int>mp;

struct SuffixAutoMaton
{
    //vectorright[N<<1];
    int ch[N<<1][26],fail[N<<1],len[N<<1],size[N<<1],k[N<<1],c[N<<1];
    int last,tot;
    void init()
    {
        last=tot=1;memset(ch[1],0,sizeof ch[1]);
    }
    void ins(int c,int pos)
    {
        int p=last;
        int np=++tot;
        last=np;
        len[np]=len[p]+1;
        memset(ch[tot],0,sizeof ch[tot]);
        for(;p&&!ch[p][c];p=fail[p])
            ch[p][c]=np;
        if(!p)
            fail[np]=1;
        else
        {
            int q=ch[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else
            {
                int nq=++tot;
                len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;ch[p][c]==q;p=fail[p])
                ch[p][c]=nq;
            }
        }
        size[np]=1;
       // right[np].push_back(pos);
    }
    void build(int n)
    {
        init();
        int ans=-1;
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);
        for(int i=1;i<=tot;i++) c[len[i]]++;
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;

        for(int i=tot;i;i--) {
            int now=k[i];
            size[fail[now]]+=size[now];
            if(size[now]>1)
            {
                ans=max(ans,size[now]*len[now]);
            }
        }
        cout<<ans<<endl;
    }
}sam;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    sam.build(n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

后记，SAM十分神奇，记录了几个关键的信息可以推出很多很多很多东西，所以多见题目，多看看能用在什么地方才是熟练应用SAM的关键。