mydcwfy's Blog

后缀自动机（SAM）

Posted on
Symbols count in article: 4.8k Reading time ≈ 10 mins.

写得比较差，建议看另一篇。

后缀自动机(SAM)

1. 主要思想

可以类比于 Trie，但它是一个有向无环图。

可以用来存储一个串的所有子串。

2. 性质

从起点出发，从普通边，可以得到所有子串。

同时，所有边和点的数量在 $O(n)$ 级别。

终点就是包含后缀的点，同时每一个点对应的是不止一个子串。

但所有每一个点对应的子串满足：按长度降序排序后，我们发现每一个串都是前面一个串的后缀。

还有一种边：$Link/Father$。

这种边构成一棵树。

将一个点所对应的最短的子串的首字母去掉，得到的子串所对应的节点，再由原来节点指向这个节点。

首先定义 $endpos(s)$ 为子串 s 在原串所有出现的位置（尾字母）下标集合。

如果有两个子串的 $endpos$ 相同，则我们可以将其看为一个等价类。

SAM 的状态与所有的等价类一一对应。

证明1：如果 $|s1|\leq|s2|$，则 $s1$ 是 $s2$ 的后缀当且仅当 $endpos(s1) \supseteq endpos(s2)$。

$s1$ 不是 $s2$ 的后缀当且仅当 $endpos(s1)\cap endpos(s2)= \varnothing$。

这两个易证。

证明2：两个不同子串的 $endpos$ 要么包含要么无交集。

易得，如果不为交集，那么必有一个 $pos$ 使两个都满足，则必有一个是另一个的子集。

证明3： 对于每一个等价类 $st$，最长的子串为 $longest$，最短的为 $shortest$，若 $shortest\leq |s|\leq longest$，则 $s$ 也是属于该等价类。

3. 构造方法

本人能力不够，也是云里雾里，只能帮到这了（ 逃 ）。

自己去理解吧。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int N=2e6+10;

struct Node{
    int len,fa;
    int ch[26];
}tr[N];
char str[N];
ll f[N],ans;
int h[N],e[N],ne[N],idx,last=1,tot=1;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void extend(int c)
{
    int p=last;int np=++tot;
    f[tot]=1;
    tr[np].len=tr[p].len+1;
    for (;p&&!tr[p].ch[c];p=tr[p].fa) tr[p].ch[c]=np;
    last=tot;
    if (!p) tr[np].fa=1;
    else{
        int q=tr[p].ch[c];
        if (tr[q].len==tr[p].len+1) tr[np].fa=q;
        else{
            int nq=++tot;
            tr[nq]=tr[q],tr[nq].len=tr[p].len+1;
            tr[q].fa=tr[np].fa=nq;
            for (;p&&tr[p].ch[c]==q;p=tr[p].fa) tr[p].ch[c]=nq;
        }
    }
}

void dfs(int x)
{
    for (int i=h[x];~i;i=ne[i])
    {
        dfs(e[i]);f[x]+=f[e[i]];
    }
    if (f[x]>1) ans=max(ans,f[x]*tr[x].len);
}

int main()
{
    scanf("%s",str);
    for (int i=0;str[i];++i) extend(str[i]-'a');
    memset(h,-1,sizeof h);
    for (int i=2;i<=tot;++i) add(tr[i].fa,i);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

4. 例题

T1：玄武密码

题目传送门 Luogu

题目传送门 AcWing

比模板还要裸。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=2e7+10;

struct Node{
    int fa,len;
    int ch[4];
}tr[N];
int last=1,tot=1;
char str[N];

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

int get(char c)
{
    switch (c)
    {
        case 'W':return 0;
        case 'N':return 1;
        case 'E':return 2;
        case 'S':return 3;
    }
}

void dfs()
{
    int p=1,i;
    for (i=0;str[i]&&tr[p].ch[get(str[i])];++i) p=tr[p].ch[get(str[i])];
    printf("%d\n",i);
    return;
}

int main()
{
    int n,m;
    cin>>n>>m;
    scanf("%s",str);
    for (int i=0;i<n;++i) extend(get(str[i]));
    while (m--)
    {
        scanf("%s",str);
        dfs();
    }
    return 0;
}

T2：最长公共子串

题目传送门 AcWing

题目传送门 LOJ

将第一个建后缀自动机，和后面的进行比较即可。

注意要标记回传，否则更新可能不及时。

注意其中的最大最小：

  1. 每一次走到一个节点时，应该和当前的取最大值。
  2. 不同的字符串之间，一个节点的值应取最小值。
  3. 最后得出答案时，应该把不同的节点所保存的值取最大输出。
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
79
80
81
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10,INF=0x3f3f3f3f;

struct Node{
    int len,fa;
    int ch[26];
}tr[2*N];
int last=1,tot=1,now[N],ans[N];
char str[N];
int h[N],e[N],ne[N],idx;

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

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tree(int x)
{
    for (int i=h[x];~i;i=ne[i])
    {
        tree(e[i]);
        now[x]=max(now[x],now[e[i]]);
    }
}

void calc()
{
    int i,p=1,t=0;
    memset(now,0,sizeof now);
    
    for (i=0;str[i];++i)
    {
        int c=str[i]-'a';
        while (p>1&&!tr[p].ch[c]) p=tr[p].fa,t=tr[p].len; 
        if (tr[p].ch[c]) p=tr[p].ch[c],t++;
        now[p]=max(now[p],t);
    }
    tree(1);
    for (int i=1;i<=tot;++i) ans[i]=min(ans[i],now[i]);
}

int main()
{
    int n;
    cin>>n;n--;
    scanf("%s",str);memset(h,-1,sizeof h);
    for (int i=0;str[i];++i) extend(str[i]-'a');
    for (int i=1;i<=tot;++i) ans[i]=tr[i].len;
    for (int i=2;i<=tot;++i) add(tr[i].fa,i);
    while (n--)
    {
        scanf("%s",str);
        calc();
    }
    int finalres=0;
    for (int i=1;i<=tot;++i) finalres=max(finalres,ans[i]);
    cout<<finalres<<endl;
}