后缀自动机(SAM) 学习笔记

2024-02-01 21:39:16

最近学了SAM已经SAM的比较简单的应用，SAM确实不好理解呀，记录一下。

这里提一下后缀自动机比较重要的性质：

1，SAM的点数和边数都是O(n)级别的，但是空间开两倍。

2，SAM每个结点代表一个endpos，每个endpos有可能代表多个字串(当然这些字串的endpos相等)，且这些字串的长度呈一个梯形。

3，令tree[x].len为点x代表的所有字串中长度最长的,tree[x].short为最短的，那么tree[x].short=(tree[fa].len)+1，根据这条性质其实tree[x].short就不用算了可以直接由fa得到。

4，SAM的一条边代表往后添加一个字符，且路径和字串一一对应，那么就得到路径数等于字串数。

5，在parent树上，x的endpos大小等于x的所有儿子y的endpos大小+1，那么就可以通过建树之后一次dfs计算所有点的endpos大小。

6，第2点说明每个状态endpos代表的长度区间为len[fa[s]]->len[s]]，那么要求所有本质不同的串的个数就是∑tlen[t]−len[fa[t]] 。

 

模板题：洛谷P3804

题目要求出现次数不为1(即endpos大小不为1)的时候计算出现次数*字串大小最大。首先肯定要计算endpos大小（这里用的是建树之后dfs的计算办法），然后虽然每个endpos应该有多个字串，但是题目要求计算最大值，所以只看endpos最长的那个字串(tree[x].len)就可以了。

后缀自动机(SAM) 学习笔记
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,tot=1,las=1;
char s[N];
struct NODE {
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}tree[N];

int cnt=0,head[N],nxt[N],to[N];
void add_edge(int x,int y) {
    nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt;
} 

long long ep[N],ans;  //ep是结点endpos大小 
void insert(int c) {  //字符插入到SAM中 
    int p=las,np=las=++tot;ep[tot]=1;
    tree[np].len=tree[p].len+1;
    for (;p&&!tree[p].ch[c];p=tree[p].fa) tree[p].ch[c]=np;
    if (!p) tree[np].fa=1;
    else {
        int q=tree[p].ch[c];
        if(tree[q].len==tree[p].len+1)tree[np].fa=q;
        else {
            int nq=++tot;
            tree[nq]=tree[q];tree[nq].len=tree[p].len+1;
            tree[q].fa=tree[np].fa=nq;
            for(;p&&tree[p].ch[c]==q;p=tree[p].fa) tree[p].ch[c]=nq;
        }
    }
}

void dfs(int x) {
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        dfs(y);
        ep[x]+=ep[y];
    }
    if(ep[x]!=1)ans=max(ans,ep[x]*tree[x].len);
}

int main()
{
    scanf("%s",s); n=strlen(s);
    for(int i=0;i<n;i++) insert(s[i]-'a');  //把字符串s插入到 SAM 中 
    
    for(int i=2;i<=tot;i++) add_edge(tree[i].fa,i);  //建树计算每个点endpos大小 
    dfs(1);  //dfs计算 
    printf("%lld\n",ans);
    return 0;
}
View Code

 

SPOJ1811 LCS - Longest Common Substring

求两个字符串最长公共字串长度。把字符串s1建SAM，然后令s2在SAM上匹配。匹配过程有点儿像AC自动机，一个一个字符匹配，匹配成功就继续往下匹配，当匹配失败的时候就沿着fa往上跳然后继续匹配。

这里要注意一个小细节，匹配失败往上跳的时候如果跳到了root结点记得把匹配信息清理。

后缀自动机(SAM) 学习笔记
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,tot=1,las=1;
char s1[N],s2[N];
struct NODE {
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}tree[N];

int cnt=0,head[N],nxt[N],to[N];
void add_edge(int x,int y) {
    nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt;
} 

long long ep[N],ans;  //ep是结点endpos大小 
void insert(int c) {  //字符插入到SAM中 
    int p=las,np=las=++tot;ep[tot]=1;
    tree[np].len=tree[p].len+1;
    for (;p&&!tree[p].ch[c];p=tree[p].fa) tree[p].ch[c]=np;
    if (!p) tree[np].fa=1;
    else {
        int q=tree[p].ch[c];
        if(tree[q].len==tree[p].len+1)tree[np].fa=q;
        else {
            int nq=++tot;
            tree[nq]=tree[q];tree[nq].len=tree[p].len+1;
            tree[q].fa=tree[np].fa=nq;
            for(;p&&tree[p].ch[c]==q;p=tree[p].fa) tree[p].ch[c]=nq;
        }
    }
}

void dfs(int x) {
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        dfs(y);
        ep[x]+=ep[y];
    }
    if(ep[x]!=1)ans=max(ans,ep[x]*tree[x].len);
}

int main()
{
    scanf("%s%s",s1,s2); 
    n=strlen(s1); m=strlen(s2);
    for(int i=0;i<n;i++) insert(s1[i]-'a');  //把字符串s插入到 SAM 中 
    
    int ans=0,nowlen=0,now=1;
    for (int i=0;i<m;i++,ans=max(ans,nowlen)) {
        int p=s2[i]-'a';
        if (tree[now].ch[p]) now=tree[now].ch[p],nowlen++;
        else {
            while(now&&!tree[now].ch[p]) now=tree[now].fa;  //失配沿着fa继续匹配 
            if (now==0) now=1,nowlen=0;  //注意这里 
            else nowlen=tree[now].len+1,now=tree[now].ch[p];
        }
    }
    cout<<ans<<endl;
    return 0;
}
View Code

 

SPOJ7258 SUBLEX - Lexicographical Substring Search(后缀自动机)

给出一个串求它的所有字串中第k小的字串（本质相同的字串只算一个）。

根据上面提到的SAM的路径数等于字串个数，我们可以先求出以每个点为起点的路径数(即得到每个点为起点的字串数)。然后常规套路像在搜索树上一边剪枝修改k一边搜索最终得到答案。

这里要注意，因为本质相同算一个，所以每个点初始值就是1。

后缀自动机(SAM) 学习笔记
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,tot=1,las=1;
char s[N];
struct NODE {
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}tree[N];

void insert(int c) {  //字符插入到SAM中 
    int p=las,np=las=++tot;
    tree[np].len=tree[p].len+1;
    for (;p&&!tree[p].ch[c];p=tree[p].fa) tree[p].ch[c]=np;
    if (!p) tree[np].fa=1;
    else {
        int q=tree[p].ch[c];
        if(tree[q].len==tree[p].len+1)tree[np].fa=q;
        else {
            int nq=++tot;
            tree[nq]=tree[q];tree[nq].len=tree[p].len+1;
            tree[q].fa=tree[np].fa=nq;
            for(;p&&tree[p].ch[c]==q;p=tree[p].fa) tree[p].ch[c]=nq;
        }
    }
}

int sub[N];
void toposort() {
    static int c[N],rk[N];
    for (int i=1;i<=tot;i++) c[tree[i].len]++;
    for (int i=1;i<=n;i++) c[i]+=c[i-1];
    for (int i=tot;i;i--) rk[c[tree[i].len]--]=i;  //前3步桶排序 
    for (int i=1;i<=tot;i++) sub[i]=1;  //本质相等只算一个，初始值为1 
    for (int i=tot;i;i--)
        for (int j=0;j<26;j++)
            sub[rk[i]]+=sub[tree[rk[i]].ch[j]]; //该点路径数等于它所有儿子路径数和 
}

void solve(int k) {
    int now=1;
    while (k) {
        if (now!=1) k--;
        if (k<=0) break;
        for (int i=0;i<26;i++) 
            if (sub[tree[now].ch[i]]<k) k-=sub[tree[now].ch[i]];
            else { putchar(i+'a'); now=tree[now].ch[i]; break; } 
    }
}

int main()
{
    scanf("%s",s); n=strlen(s);
    for(int i=0;i<n;i++) insert(s[i]-'a');  //把字符串s插入到 SAM 中 
    
    toposort();  //求DAG某个点为起点的路径数 
    int T,q; cin>>T;
    while (T--) {
        scanf("%d",&q);
        solve(q); puts("");
    }
    return 0;
}
View Code

 

BZOJ-3998 / 洛谷P3975 弦论 跟上题差不多,只不过是本质相同字串要算多次，所以每个点的初始值不是1而是endpos的大小。其他不用怎么变。 这题按道理字串个数要用long long。但是在BZOJ上用long long有可能超时，用int就能过。。。 后缀自动机(SAM) 学习笔记
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,tot=1,las=1;
char s[N];
struct NODE {
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}tree[N];
 
int ep[N],sub[N];
void insert(int c) {  //字符插入到SAM中 
    int p=las,np=las=++tot; ep[tot]=1;
    tree[np].len=tree[p].len+1;
    for (;p&&!tree[p].ch[c];p=tree[p].fa) tree[p].ch[c]=np;
    if (!p) tree[np].fa=1;
    else {
        int q=tree[p].ch[c];
        if(tree[q].len==tree[p].len+1)tree[np].fa=q;
        else {
            int nq=++tot;
            tree[nq]=tree[q];tree[nq].len=tree[p].len+1;
            tree[q].fa=tree[np].fa=nq;
            for(;p&&tree[p].ch[c]==q;p=tree[p].fa) tree[p].ch[c]=nq;
        }
    }
}
 
int c[N],rk[N];
void toposort(int opt) {
    for (int i=1;i<=tot;i++) c[tree[i].len]++;
    for (int i=1;i<=n;i++) c[i]+=c[i-1];
    for (int i=tot;i;i--) rk[c[tree[i].len]--]=i;  //前3步桶排序 
     
    if (opt==0)
        for (int i=2;i<=tot;i++) ep[i]=1;  //本质相等只算一个，初始值为1 
    if (opt==1) 
        for (int i=tot;i>1;i--) ep[tree[rk[i]].fa]+=ep[rk[i]];   //本质相等算多个，初始值为endpos大小  
    for (int i=2;i<=tot;i++) sub[i]=ep[i];
    for (int i=tot;i;i--)
        for (int j=0;j<26;j++)
            sub[rk[i]]+=sub[tree[rk[i]].ch[j]]; //该点路径数等于它所有儿子路径数和 
}
 
void solve(int k) {
    int now=1;
    if (k>sub[1]) { puts("-1"); return; }
    while (k) {
        if (now!=1) k-=ep[now];
        if (k<=0) break;
        for (int i=0;i<26;i++) 
            if (sub[tree[now].ch[i]]<k) k-=sub[tree[now].ch[i]];
            else { putchar(i+'a'); now=tree[now].ch[i]; break; } 
    }
}
 
int main()
{
    scanf("%s",s); n=strlen(s);
    for(int i=0;i<n;i++) insert(s[i]-'a');  //把字符串s插入到 SAM 中 
     
    int opt,q; cin>>opt>>q;
    toposort(opt);  //求DAG某个点为起点的路径数 
    solve(q);
    return 0;
}
View Code

 

 HDU-4622 Reincarnation 题意：给出一个字符串，有多次询问[l,r]，要求求字符串[l,r]字串的所有本质不同的字串个数。 解法：根据上面第6点，当我们把SAM建出来就可以通过计算sigma(tree[x].len-tree[x.fa].len)得到本质不同字串个数。但是本题要求区间不同字串个数，一看数据量2000，我们做n^2的预处理：枚举区间左端点i开始建SAM然后从左端点开始往后逐一把每个字符j加入到SAM，那么此时得到的SAM就是区间[i,j]的SAM。但是我们不能每次求出SAM暴力计算sigma(tree[x].len-tree[x.fa].len)，明显超时。观察发现每插入一个字符对答案多造成的贡献就是插入字符的tree[x].len-tree[x.fa].len，所以逐一累加即可。 后缀自动机(SAM) 学习笔记
#include<bits/stdc++.h>
using namespace std;
const int N=4e3+10;
int n,tot=1,las=1,sum;
char s[N];
struct NODE {
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}tree[N];
 
int ep[N],ans[2010][2010];
void insert(int c) {  //字符插入到SAM中 
    int p=las,np=las=++tot; ep[tot]=1;
    tree[np].len=tree[p].len+1;
    for (;p&&!tree[p].ch[c];p=tree[p].fa) tree[p].ch[c]=np;
    if (!p) tree[np].fa=1;
    else {
        int q=tree[p].ch[c];
        if(tree[q].len==tree[p].len+1)tree[np].fa=q;
        else {
            int nq=++tot;
            tree[nq]=tree[q];tree[nq].len=tree[p].len+1;
            tree[q].fa=tree[np].fa=nq;
            for(;p&&tree[p].ch[c]==q;p=tree[p].fa) tree[p].ch[c]=nq;
        }
    }
    sum+=tree[np].len-tree[tree[np].fa].len;
}
 
int main()
{
    int T; cin>>T;
    while (T--) {
        scanf("%s",s+1); n=strlen(s+1);
        for (int i=1;i<=n;i++) {
            sum=0;
            for (int j=i;j<=n;j++) {
                insert(s[j]-'a');
                ans[i][j]=sum;
            }
            for (int j=1;j<=tot;j++) {
                tree[j].fa=tree[j].len=0;
                memset(tree[j].ch,0,sizeof(tree[j].ch));
            }
            tot=1; las=1;
        }
        int q; cin>>q;
        while (q--) {
            int l,r; scanf("%d%d",&l,&r);
            printf("%d\n",ans[l][r]);
        }
    }
    return 0;
}
View Code

 

 
上一篇：P5546-[POI2000]公共串【SAM】


下一篇：LIO-SAM论文翻译