浅谈后缀自动机：概述，构建与简单应用

栏目: 数据库 · 发布时间: 5年前

内容简介：不得不说我是真的弱，寒假里颓废的一批，PKUWC爆炸之后过了一个多月才来学这个东西，看到巫蛊偶大神一年前各种后缀自动机神仙题的AC记录，感觉完全被他吊打。后缀自动机是一种应用十分广泛的处理字符串问题的数据结构，大多数目前难度较高的字符串题都要用到这个东西。本文简单讲述后缀自动机的原理与构造，并讲解一点其简单应用。本人觉得这个东西还是比较抽象的，首先需要感性理解，然后再去看一些公式之类的东西比较好。本人之前直接刚论文结果搞了很长时间还没搞懂。本文严谨性比较差，一些精确的定义可以看完本文之后再去看论文。

前言

不得不说我是真的弱，寒假里颓废的一批，PKUWC爆炸之后过了一个多月才来学这个东西，看到巫蛊偶大神一年前各种后缀自动机神仙题的AC记录，感觉完全被他吊打。

后缀自动机是一种应用十分广泛的处理字符串问题的数据结构，大多数目前难度较高的字符串题都要用到这个东西。本文简单讲述后缀自动机的原理与构造，并讲解一点其简单应用。

本人觉得这个东西还是比较抽象的，首先需要感性理解，然后再去看一些公式之类的东西比较好。本人之前直接刚论文结果搞了很长时间还没搞懂。本文严谨性比较差，一些精确的定义可以看完本文之后再去看论文。

后缀树

后缀树是一个和后缀自动机密切关联的东西，由于它特别好理解，所以先放在前面了。

后缀树你可以理解为将一个串全部的后缀扔到一个trie树里面去，但是如果串长为n，那么这棵trie树上的节点最坏情况下可以达到$\Theta(n^2)$的级别。

举个例子，比如设字符串S=”ababaa”，它的后缀有：

aa,

baa,

abaa,

babaa,

ababaa,

那么这棵trie树是长这个样子的：

可以发现，如果一个串是S的子串，那么它能在这棵trie树上最后能到一个节点上，如果它是S的一个后缀，那么能走到一个黑色的节点上面。

然后我们发现，其实这棵树上有用的节点并不多，我们可以建立这些黑色节点的虚树来压缩节点（也就是删掉所有只有一个儿子的白色节点）。

可以证明这棵树的节点个数是$O(n)$的，我们可以发现一些性质：

1.假定我们刚才删去的节点表示的子串都被合并到了它最近的子孙上，那么此时一个点表示的子串有一个性质：这些子串在字符串中出现次数相同，且出现次数均为该子树中黑色节点的个数。

2.两个子串的LCP（最长公共前缀）相当于这两个子串在后缀树上的LCA（最近公共祖先）所代表的最长子串长度。

…….

至于如何快速构建后缀树，后缀树原本的构建方法非常麻烦，这里不作介绍，现在我们可以利用后缀自动机来进行构建，代码复杂度会变得简单很多。

后缀树给了我们一个启发：如果要表示一个字符串所有的子串或者后缀，并不需要很多节点，因为很多子串的相同性质可以把那些点合并起来。

后缀自动机

概述

现在请你暂时忘了后缀树，我们来看后缀自动机。

后缀自动机就是一个可以接受所有后缀的有限自动机。有限自动机（这个理解不严谨）你可以理解为一张有向图，然后里面有一个起始点，另外每个点对于字符集中的每一个字符都有唯一对应的出边，拿一个串在上面从起始点开始每次按下一位的字符走到对应的边上，走完整个串停在的节点就是其终止状态，我们可以通过终止状态判断它的是什么样的串。（AC自动机就是一个很好的例子）

所以如果你拿一个串在后缀自动机上跑，如果它最后听在的位置是一个你标记过的节点，那么它是一个后缀，否则如果它跑到外面去了或者停在了你没有标记的节点上面它就不是一个原串的后缀）。

当然，直接扔进trie树里面这个是会节点数太多的（之前已经说过了），我们还是可以用类似的方法，只不过这个和后缀树执行不一样的压缩方式。（这里我们首先不去标记哪些位置是后缀）

现在，我们对于所有的子串，如果删掉首字母之后其在原串中出现次数不变，那么我们把这该子串与其删掉首字母之后的子串缩在一起，如果出现次数变化了，那么就令该节点的fail为其删掉首字母之后的子串所对的节点。比如对于字符串”abb”它的后缀自动机大概是长这样的（黑边表转移边，红边表示fail）：

“aba”大概是长这样的：

其空间复杂度是$O(n)$的，证明方法很多，我们可以从后面构造的角度上来证明它。

构建后缀自动机

构建后缀自动机有一个时间复杂度为$O(n|\sum|$)的算法（如果字符集很大可以使用平衡树（C++可以直接用map）把他变成$O(n\lg |\sum|)$），代码实现比较简单，这里来了解一下。

算法流程

我们考虑对于一个字符串S，如果已经构建出了$S_1..S_{n-1}$的后缀自动机如何构造出$S_1..S_n$的后缀自动机。

你可以先按照定义随便找一个串试一试，将字符依次插入，然后把后缀自动机画出来看一看。

接下来看一下这个建自动机的流程。

首先新建一个节点x表示$S_1..S_n$对应的节点。

我们考虑哪些节点需要因为最后一个字符$S_n$的而改变转移边。令$S_1..S_{n-1}$的子串对应的节点为last，根据前面的说明，当然是last，last的fail，last的fail的fail，last的fail的fail的fail…

那我们就一个个遍历上去，如果没有$S_n$这个字符的转移，那么直接把转移边接到x上好了。

可以发现一但有了转移边，那么再上面的节点也是有转移边的。

所以我们接下来考虑如果有转移边了怎么办。

我们令第一个出现转移边的节点为t。那么这两排东西可能是长这个样子的。（红边表示fail，黑边表示$S_n$的转移边）

那么显然x的fail需要有的最长子串就在这个节点t里面，但是t里面可能还有更长的子串。那么如何判断还有更长的子串呢？我们只需要在做的时候记录一下一个节点所代表的最长子串即可。如果没有更长的子串，那么直接把x的fail设成t就好了。如果有了呢？一个简单的想法就是讲该节点裂开来，变成两个节点。我们令裂出来的节点为q。

那么x的fail为q，t的fail也为q，我们把对应的转移边改过来就好了。由于q只能从last的fail那一片转移过来所以对其他点的转移边没有影响。现在这张图大概长这样了：

其他点均没有影响，所以我们就做完了。

代码

代码比较简单，打两遍基本上就记住了。(这里默认字符集为26，而且是0..25)

int insert(int st,int p,int c){
    int x=++top;
    tree[x].max=tree[p].max+1;
    for(int i=0;i<26;++i) tree[x].son[i]=0;
    for(;p>0&&tree[p].son[c]==0;p=tree[p].fail)
        tree[p].son[c]=x;
    if(p==0) tree[x].fail=st;
    else{
         int t=tree[p].son[c];
         if(tree[p].max+1==tree[t].max) tree[x].fail=t;
         else{
             int q=++top;
             for(int i=0;i<26;++i)
                   tree[q].son[i]=tree[t].son[i];
             tree[q].fail=tree[t].fail,tree[t].fail=q;
             tree[q].max=tree[p].max+1,tree[x].fail=q;
             for(;tree[p].son[c]==t;p=tree[p].fail)
                tree[p].son[c]=q;
        }
    }
    return x;
}

时空复杂度分析

空间复杂度很简单，因为每次最多开两个点，所以开两倍空间就好了。

接下来来证明时间复杂度上界为$O(n|\sum|)$

我们令此时表示$S[1:n]$的这个串表示的点为x，$cnt(x)$表示x的fail个数（即是其后缀的出现次数不同的子串个数），$fail(x)$表示其fail，$maxlen(x)$表示其表示的最大子串长度。

我们只需要定义势能函数（常数忽略）：

$\Phi(D)=cnt(x)+maxlen(fail(x))$

考虑我们之前算法中玄学复杂度的地方：一个是寻找第一个找不到转移边的点，另外一个是更新last的fail们的转移边。

对于第一个，每次寻找一个必定会减少fail的个数，用这个$cnt(x)$去吃掉就好了，每次新建节点后$maxlen(fail(x))$至多增加1，但是每次改变转移边的次数不会超过其maxlen的减少值（因为多一次改变就意味这至少多一个子串被划到了t里面去）。

一开始势能函数为0，最后肯定不小于0，所以合法。我们就证完了。

其他定义与性质

定义一个串的$Right$集合为其作为后缀出现过的前缀的右端点的集合。比如说”abaa”这个串，$Right(“a”)=\lbrace 1,3,4 \rbrace$，$Right(“aa”)=\lbrace 4\rbrace$，可以证明一个串在原串中的出现次数为$Right$集合的大小，一个点表示的所有串$Right$集合相同。

一条路径和一个子串一一对应。

一个自动机本质不同的子串个数为$\sum maxlen(x)-maxlen(fail(x))$，其实就相当于把所有节点表示的串的个数加起来。

后缀自动机的fail形成了一棵树，这棵树正好是其反串的后缀树，所以我们可以使用后缀自动机来建后缀树。

一个原串前缀属于的点我们称为np节点，$Right$集合大小为其fail树中np节点个数（非常显然）

广义后缀自动机

广义后缀自动机简单来说就是把一堆字符串扔到同一个后缀自动机里面去，做法是每扔一个之后重新从源点开始接字符，至于复杂度，我们可以考虑将这些字符串接在一起然后用不同的分隔符隔开之后建后缀自动机的复杂度。我们发现此时的构建过程与现在这个做法非常像，大概就可以证一下了。代码方面有一点要注意，就是有可能上一个点已经有出边了，这时候我们只需要判一下需不需要裂点，如果需要的话裂个点就好了。代码：

    int insert(int st,int p,int c){
        if(tree[p].son[c]==0){
            int x=++top;
            tree[x].max=tree[p].max+1;
            for(;p>0&&tree[p].son[c]==0;p=tree[p].fail)
                tree[p].son[c]=x;
            if(p==0) tree[x].fail=st;
            else{
                int t=tree[p].son[c];
                if(tree[p].max+1>=tree[t].max) tree[x].fail=t;
                else{
                    int q=++top;
                    for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                    tree[q].fail=tree[t].fail,tree[t].fail=q;
                    tree[q].max=tree[p].max+1,tree[x].fail=q;
                    for(;tree[p].son[c]==t;p=tree[p].fail)
                        tree[p].son[c]=q;
                }
            }
            return x;
        }else{
            int t=tree[p].son[c];
            if(tree[p].max+1>=tree[t].max) return t;
            else{
                int q=++top;
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail,tree[t].fail=q;
                tree[q].max=tree[p].max+1;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
                return q;
            }
        }   
    }

例题

例题1：[模板]后缀自动机

[洛谷P3804][模板]后缀自动机

就是求$\max \lbrace |\Right(x)|maxlen(x) \rbrace

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=5+1e6;
namespace SAM{
    struct Node{
        int son[26],max,fail,cnt;
    }tree[MAX_N*2];
    int top=1,last=1;
    void insert(int c){
        int nw=++top,p=last;
        tree[nw].max=tree[last].max+1;
        tree[nw].cnt=1;
        for(;p!=0&&tree[p].son[c]==0;p=tree[p].fail)
            tree[p].son[c]=nw;
        if(p==0) tree[nw].fail=1;
        else{   
            int t=tree[p].son[c];
            if(tree[p].max+1>=tree[t].max)
                tree[nw].fail=t;
            else{
                int q=++top;
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail;
                tree[t].fail=q;
                tree[q].max=tree[p].max+1;
                tree[nw].fail=q;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
            }
        }
        last=nw;
    }
    int q[MAX_N*2],rd[MAX_N*2];
    void solve(){
        int h=1,t=0;
        for(int i=1;i<=top;++i) rd[tree[i].fail]++;
        for(int i=1;i<=top;++i)
            if(rd[i]==0) q[++t]=i;
        while(h<=t){
            int x=q[h++],y=tree[x].fail;
            tree[y].cnt+=tree[x].cnt;
            --rd[y];
            if(rd[y]==0) q[++t]=y;
        }
        ll ret=0;
        for(int i=1;i<=top;++i)
            if(tree[i].cnt>1)
                ret=max(ret,(ll)tree[i].cnt*tree[i].max);
        printf("%lld",ret);
    }
}
char s[MAX_N];
int main(){
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;++i) SAM::insert(s[i]-'a');
    SAM::solve();
    return 0;
}

例题2：[洛谷P4248][AHOI2013]差异

[洛谷P4248][AHOI2013]差异

把前面两个长度的和直接算，考虑到lcp相当于后缀树上的lca的最长子串长度，所以直接把后缀树建出来然后每个点作为lca的代价算一算就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=5+1e6;
namespace SAM{
    struct Node{
        int son[26],max,fail,cnt;
    }tree[MAX_N*2];
    int top=1,last=1;
    void insert(int c){
        int nw=++top,p=last;
        tree[nw].max=tree[last].max+1;
        tree[nw].cnt=1;
        for(;p!=0&&tree[p].son[c]==0;p=tree[p].fail)
            tree[p].son[c]=nw;
        if(p==0) tree[nw].fail=1;
        else{   
            int t=tree[p].son[c];
            if(tree[p].max+1>=tree[t].max)
                tree[nw].fail=t;
            else{
                int q=++top;
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail;
                tree[t].fail=q;
                tree[q].max=tree[p].max+1;
                tree[nw].fail=q;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
            }
        }
        last=nw;
    }
}
ll ret;
namespace STREE{
    struct Edge{ int to,nxt; }edge[MAX_N];
    int head[MAX_N],top_edge=-1,sz[MAX_N];
    void add_edge(int x,int y){
        edge[++top_edge]=(Edge){y,head[x]};
        head[x]=top_edge;
    }
    void dfs(int x){
        sz[x]=SAM::tree[x].cnt;
        for(int j=head[x];j!=-1;j=edge[j].nxt){
            int y=edge[j].to;
            dfs(y);
            ret-=2ll*sz[x]*sz[y]*SAM::tree[x].max;
            sz[x]+=sz[y];
        }
    }
    void build(){
        memset(head,-1,sizeof(head));
        for(int i=1;i<=SAM::top;++i)
            add_edge(SAM::tree[i].fail,i);
    }
}
char s[MAX_N];
int main(){
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;++i) SAM::insert(s[i]-'a');
    STREE::build();
    STREE::dfs(1);
    for(int i=1;i<=n;++i) ret+=(ll)i*(n-1);
    printf("%lld",ret);
    return 0;
}

例题3：[洛谷P3975][TJOI2015]弦论

[洛谷P3975][TJOI2015]弦论

考虑后缀自动机的转移边组成了一个DAG，我们只需要算出每一个点往下走所有不同路径的带权和即可。然后类似于线段树上二分的方法算一下就好了。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=5+1e6;
namespace SAM{
    struct Edge{ int to,nxt; }edge[MAX_N*26];
    int head[MAX_N],top_edge=-1;
    void add_edge(int x,int y){
        edge[++top_edge]=(Edge){y,head[x]};
        head[x]=top_edge;
    }
    struct Node{
        int son[26],max,fail,cnt;
    }tree[MAX_N];
    int top=1,last=1;
    void insert(int c){
        int x=++top,p=last;
        tree[x].max=tree[p].max+1,tree[x].cnt=1;
        for(;p!=0&&tree[p].son[c]==0;p=tree[p].fail)
            tree[p].son[c]=x;
        if(p==0) tree[x].fail=1;
        else{
            int t=tree[p].son[c];
            if(tree[p].max+1>=tree[t].max) tree[x].fail=t;
            else{
                int q=++top;
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail,tree[t].fail=q;
                tree[q].max=tree[p].max+1,tree[x].fail=q;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
            }
        }
        last=x;
    }
    int s1[MAX_N],s2[MAX_N];
    void bfs1(){
        static int q[MAX_N],rd[MAX_N]; int h=1,t=0;
        for(int i=1;i<=top;++i) rd[tree[i].fail]++;
        for(int i=1;i<=top;++i) if(rd[i]==0) q[++t]=i;
        while(h<=t){
            int x=q[h++],y=tree[x].fail;
            tree[y].cnt+=tree[x].cnt;
            --rd[y];
            if(rd[y]==0) q[++t]=y;
        }
    }
    void bfs2(){
        static int q[MAX_N],rd[MAX_N]; int h=1,t=0;
        for(int i=1;i<=top;++i) 
            for(int j=head[i];j!=-1;j=edge[j].nxt)
                ++rd[edge[j].to];
        for(int i=1;i<=top;++i) rd[i]?0:q[++t]=i;
        while(h<=t){
            int x=q[h++];
            if(x>1){
                s1[x]+=1;
                s2[x]+=tree[x].cnt;
            }
            for(int j=head[x];j!=-1;j=edge[j].nxt){
                int y=edge[j].to;
                s1[y]+=s1[x];
                s2[y]+=s2[x];
                --rd[y];
                if(rd[y]==0) q[++t]=y;
            }
        }
    }
    void init(){
        memset(head,-1,sizeof(head));
        for(int i=1;i<=top;++i)
            for(int j=0;j<26;++j)
                if(tree[i].son[j]!=0)
                    add_edge(tree[i].son[j],i);
        bfs1();
        bfs2();
    }
    void query(int k,int t){
        if(t==0&&k>s1[1]||t==1&&k>s2[1]){
            puts("-1");
            return;
        }
        int x=1;
        while(x==1||k>(t?tree[x].cnt:1)){
            if(x>1) k-=(t?tree[x].cnt:1);
            for(int i=0;i<26;++i){
                if(tree[x].son[i]!=0){
                    int key=t?s2[tree[x].son[i]]:s1[tree[x].son[i]];
                    if(k<=key){
                        putchar(i+'a');
                        x=tree[x].son[i];
                        break;
                    }else k-=key;
                }
            }
        }
        puts("");
    }
}
char s[MAX_N];
int main(){
    scanf("%s",s);
    int k,t,n=strlen(s); scanf("%d%d",&t,&k);
    for(int i=0;i<n;++i) SAM::insert(s[i]-'a');
    SAM::init();
    SAM::query(k,t);
    return 0;
}

例题4：[洛谷P5212]SubString

[洛谷P5212]SubString

加个LCT维护一下Right集合大小就好了，略微卡常，开O2可过。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=4e6+5;
struct LCT{
    struct Node{
        int son[2],fa,key,sum,sz,tag1;
        bool tag;
    }tree[MAX_N];
    int stk[MAX_N],top_stk;
    void new_node(int x,int key){
        tree[x]=(Node){{0,0},0,key,key,1,false,false};
    }
    void up(int x){
        tree[x].sz=1+tree[tree[x].son[0]].sz+tree[tree[x].son[1]].sz;
        tree[x].sum=tree[tree[x].son[0]].sum
            +tree[tree[x].son[1]].sum+tree[x].key;
    }
    void put_tag(int x,int tag1,bool tag){
        if(!x) return;
        if(tag){
            swap(tree[x].son[0],tree[x].son[1]);
            tree[x].tag^=1;
        }
        tree[x].sum+=tag1*tree[x].sz;
        tree[x].key+=tag1;
        tree[x].tag1+=tag1;
    }
    void down(int x){
        put_tag(tree[x].son[0],tree[x].tag1,tree[x].tag);
        put_tag(tree[x].son[1],tree[x].tag1,tree[x].tag);
        tree[x].tag1=0,tree[x].tag=false;
    }
    bool is_rt(int x){
        return (tree[tree[x].fa].son[0]!=x)&&(tree[tree[x].fa].son[1]!=x);
    }
    void rotate(int x){
        int y=tree[x].fa,z=tree[y].fa,k=tree[y].son[1]==x;
        if(!is_rt(y)) tree[z].son[tree[z].son[1]==y]=x;
        tree[x].fa=z,tree[tree[x].son[!k]].fa=y,tree[y].fa=x;
        tree[y].son[k]=tree[x].son[!k],tree[x].son[!k]=y;
        up(y);
    }
    void splay(int x){
        stk[top_stk=1]=x;
        for(int i=x;!is_rt(i);i=tree[i].fa) stk[++top_stk]=tree[i].fa;
        for(;top_stk>0;--top_stk) down(stk[top_stk]);
        while(!is_rt(x)){
            int y=tree[x].fa,z=tree[y].fa;
            if(!is_rt(y))
                rotate((tree[z].son[0]==y)^(tree[y].son[0]==x)?x:y);
            rotate(x);
        }
        up(x);
    }
    void access(int x){
        for(int i=0;x;i=x,x=tree[x].fa)
            splay(x),tree[x].son[1]=i,up(x);
    }
    void make_root(int x){
        access(x),splay(x),put_tag(x,0,true);
    }
    void link(int x,int y){
        make_root(x),make_root(y),tree[y].fa=x;
    }
    void cut(int x,int y){
        make_root(x),access(x),splay(y);
        tree[y].fa=0;
    }
    int split(int x,int y){
        make_root(x),access(y),splay(y);
        return y;
    }
    int query(int x){
        return tree[split(x,x)].sum;
    }
    void change(int x,int y,int key){
//      printf("<%d %d>",x,y);
        put_tag(split(x,y),key,false);
    }
}lct;
namespace SAM{
    struct Node{
        int son[26],max,fail;
    }tree[MAX_N];
    int top=1,last=1;
    void insert(int c){
        int x=++top,p=last;
        tree[x].max=tree[p].max+1;
        lct.new_node(x,0);
        for(;p>0&&tree[p].son[c]==0;p=tree[p].fail)
            tree[p].son[c]=x;
        if(p==0) tree[x].fail=1,lct.link(1,x);
        else{
            int t=tree[p].son[c]; 
            if(tree[p].max+1>=tree[t].max) 
                tree[x].fail=t,lct.link(x,t);
            else{
                int q=++top; lct.new_node(q,lct.query(t));
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                lct.cut(t,tree[t].fail);
                lct.link(q,tree[t].fail);
                lct.link(t,q);
                lct.link(x,q);
                tree[q].fail=tree[t].fail,tree[t].fail=q;
                tree[q].max=tree[p].max+1,tree[x].fail=q;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
            }
        }
        last=x;
        lct.change(1,x,1);
    }
    int query(char* s){
        int n=strlen(s),x=1;
        for(int i=0;i<n;++i)
            x=tree[x].son[s[i]-'A'];
        if(x==0) return 0;
        return lct.query(x);
    }
}
char s[MAX_N],s1[MAX_N];
int mask=0;
void decode(char* s,int mask){
    int n=strlen(s);
    for(int j=0;j<n;++j){
        mask=(mask*131ll+j)%n;
        swap(s[j],s[mask]);
    }
}
int main(){
    int q,n; scanf("%d",&q);
    scanf("%s",s),n=strlen(s);
    lct.new_node(1,0);
    for(int i=0;i<n;++i){
        SAM::insert(s[i]-'A');
//      SAM::dfs();
    }
    while(q--){
        scanf("%s%s",s1,s);
        decode(s,mask);
        if(s1[0]=='A'){
            int n=strlen(s);
            for(int i=0;i<n;++i) SAM::insert(s[i]-'A');
        }else{
            int ret=SAM::query(s);
            mask^=ret;
            printf("%d\n",ret);
        }
    }
    return 0;
}

例题6：[洛谷P3346][ZJOI2015]诸神眷顾的幻想乡

[洛谷P3346][ZJOI2015]诸神眷顾的幻想乡

由于叶子节点少，所以你需要用到的串很少，直接暴力把所有串扔到广义后缀自动机上然后搞一下就好了。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=5+5e6;
namespace SAM{
    typedef long long ll;
    struct Node{
        int son[10],max,fail;
    }tree[MAX_N];
    int top=1;
    int insert(int p,int c){
        if(tree[p].son[c]==0){
            int x=++top;
            tree[x].max=tree[p].max+1;
            for(;p>0&&tree[p].son[c]==0;p=tree[p].fail)
                tree[p].son[c]=x;
            if(p==0) tree[x].fail=1;
            else{
                int t=tree[p].son[c];
                if(tree[p].max+1>=tree[t].max) tree[x].fail=t;
                else{
                    int q=++top;
                    for(int i=0;i<10;++i) tree[q].son[i]=tree[t].son[i];
                    tree[q].fail=tree[t].fail,tree[t].fail=q;
                    tree[q].max=tree[p].max+1,tree[x].fail=q;
                    for(;tree[p].son[c]==t;p=tree[p].fail)
                        tree[p].son[c]=q;
                }
            }
            return x;
        }else{
            int t=tree[p].son[c];
            if(tree[p].max+1>=tree[t].max) return t;
            else{
                int q=++top;
                for(int i=0;i<10;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail,tree[t].fail=q;
                tree[q].max=tree[p].max+1;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
                return q;
            }
        }   
    }
    void solve(){
        ll ans=0;
        for(int i=1;i<=top;++i)
            ans+=tree[i].max-tree[tree[i].fail].max;
        printf("%lld",ans);
    }
}
int poi[MAX_N];
struct Edge{ int to,nxt; }edge[MAX_N];
int head[MAX_N],top_edge=-1,c[MAX_N],deg[MAX_N],fa[MAX_N];
void add_edge(int x,int y){
    edge[++top_edge]=(Edge){y,head[x]};
    head[x]=top_edge;
}
void dfs(int x,int pre){
    poi[x]=SAM::insert(poi[pre],c[x]);
    for(int j=head[x];j!=-1;j=edge[j].nxt){
        int y=edge[j].to;
        if(y!=pre) dfs(y,x);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    int n,d; scanf("%d%d",&n,&d);
    for(int i=1;i<=n;++i) scanf("%d",&c[i]);
    for(int i=1;i<n;++i){
        int x,y; scanf("%d%d",&x,&y);
        add_edge(x,y),add_edge(y,x);
        ++deg[x],++deg[y];
    }
    poi[0]=1;
    for(int i=1;i<=n;++i) 
        if(deg[i]==1) dfs(i,0);
    SAM::solve();
    return 0;
}

例题7：[洛谷P4770][NOI2018]你的名字

[洛谷P4770][NOI2018]你的名字

这道才是真正的毒瘤题，前面6道加起来都没这道题神仙题难。

首先考虑68分怎么做，简单来说就是有一个很长的串$S$，有很多比较短的串$T_i$你要求出对于每一个$T_i$在$S$中没有出现过的子串个数。由于$|S|$很大，所以我们每次统计答案的时候时间复杂度不能带$|S|$。

考虑枚举$T_i$的每一个前缀，求出其有多少个后缀在$S$中出现过。贪心地，从$S$后缀自动机的源点开始，我们每次要向下按转移边走一次得到下一个前缀，如果该点没有转移边，那么说明我们需要削去前面的若干个字符才能与$S$中的子串匹配，也就是我们不断往fail上跳知道有一个fail有这样的转移边，每一个前缀相同的后缀个数就相当于这样做得到该前缀时还剩余的子串长度（就是没有被削去的）的和。由于削去次数有限，所以这一步时间复杂度是$O(|T|)$的。

然后我们把这些长度放入$T_i$建出来的后缀自动机里面通过fail树DP求出相同子串个数，然后再用总的子串个数减掉相同的得到不同的。

这样我们的时间复杂度是$O(|S|+\sum |T|)$

然后考虑有$l,r$限制的情况。还是考虑之前的做法，只不过在一些点中得到的一些长度是不合法的。我们只需要找到该位置右端点在不超过r的前提下的最大值，判一下左端点在不在范围内就好了。这个我们用一个可持久化线段树维护dfs序来寻找子树内代表最右前缀的np节点即可。如果一个$T$的前缀在节点上不合法，直接削它即可。

时间复杂度$O(|S|+\sum |T|\lg |S|)$

细节比较多，代码写到精神恍惚。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=15+2e6;
int n,rt[MAX_N],top1=1;
namespace SEG{
    struct Node{
        int son[2],sz,mx;
    }tree[MAX_N*26];
    int top=0;
    void up(int x){
        tree[x].sz=tree[tree[x].son[0]].sz+tree[tree[x].son[1]].sz;
        tree[x].mx=max(tree[tree[x].son[0]].mx,tree[tree[x].son[1]].mx);
    }
    int new_node(){
        tree[++top]=(Node){{0,0},0,0};
        return top;
    }
    void change(int& x,int& y,int l,int r,int pos,int key){
        y=new_node();
        if(l==r){
            tree[y].sz=1;
            tree[y].mx=key;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid){
            tree[y].son[1]=tree[x].son[1];
            change(tree[x].son[0],tree[y].son[0],l,mid,pos,key);
        }else{
            tree[y].son[0]=tree[x].son[0];
            change(tree[x].son[1],tree[y].son[1],mid+1,r,pos,key);
        }
        up(y);
    }
    int query(int p,int l,int r,int x,int y){
        if(l==x&&r==y) return tree[p].sz;
        int mid=l+r>>1;
        if(y<=mid) return query(tree[p].son[0],l,mid,x,y);
        else if(x>mid) return query(tree[p].son[1],mid+1,r,x,y);
        else return query(tree[p].son[0],l,mid,x,mid)
                +query(tree[p].son[1],mid+1,r,mid+1,y);
    }
    int query1(int p,int l,int r,int x,int y){
        if(l==x&&r==y) return tree[p].mx;
        int mid=l+r>>1;
        if(y<=mid) return query1(tree[p].son[0],l,mid,x,y);
        else if(x>mid) return query1(tree[p].son[1],mid+1,r,x,y);
        else return max(query1(tree[p].son[0],l,mid,x,mid)
            ,query1(tree[p].son[1],mid+1,r,mid+1,y));
    }
}
namespace TREE{
    struct Edge{ int to,nxt; }edge[MAX_N];
    int head[MAX_N],top_edge=-1,dfn[MAX_N],e[MAX_N],ti=0;
    void add_edge(int x,int y){
        edge[++top_edge]=(Edge){y,head[x]};
        head[x]=top_edge;
    }
    void dfs(int x){
        dfn[x]=++ti;
        for(int j=head[x];j!=-1;j=edge[j].nxt){
            int y=edge[j].to;
            dfs(y);
        }
        e[x]=ti;
    }
    int query(int l,int r,int x){
        return SEG::query(rt[r],1,top1,dfn[x],e[x]);
           -SEG::query(rt[l-1],1,top1,dfn[x],e[x]);
    }
    int query1(int l,int r,int x){
        return SEG::query1(rt[r],1,top1,dfn[x],e[x]);
    }
}
namespace SAM{
    struct Node{
        int son[26],max,fail;
    }tree[MAX_N];
    int top=1;
    int cnt[MAX_N];
    void init(int x){
        cnt[x]=0;
        for(int i=0;i<26;++i) tree[x].son[i]=0;
        tree[x].max=0,tree[x].fail=0;
    }
    int insert(int st,int p,int c){
        int x=++top; init(x);
        tree[x].max=tree[p].max+1,cnt[x]=0;
        for(int i=0;i<26;++i) tree[x].son[i]=0;
        for(;p>0&&tree[p].son[c]==0;p=tree[p].fail)
            tree[p].son[c]=x;
        if(p==0) tree[x].fail=st;
        else{
            int t=tree[p].son[c];
            if(tree[p].max+1==tree[t].max) tree[x].fail=t;
            else{
                int q=++top; init(q);
                for(int i=0;i<26;++i) tree[q].son[i]=tree[t].son[i];
                tree[q].fail=tree[t].fail,tree[t].fail=q;
                tree[q].max=tree[p].max+1,tree[x].fail=q;
                for(;tree[p].son[c]==t;p=tree[p].fail)
                    tree[p].son[c]=q;
            }
        }
        return x;
    }
    void solve(int x,int y,int l,int r,char* s){
        int n=strlen(s),len=0;
        for(int i=0;i<n;++i){
            int c=s[i]-'a';
            y=tree[y].son[c];
            while(x>0&&tree[x].son[c]==0){
                --len;
                if(len<=tree[tree[x].fail].max) 
                    x=tree[x].fail;
            }
            ++len;
            if(x==0) x=1;
            else x=tree[x].son[c];
            while(x>1&&(TREE::query(l,r,x)==0
                ||TREE::query1(l,r,x)-len+1<l)){
                --len;
                if(len<=tree[tree[x].fail].max)
                    x=tree[x].fail;
            }
            cnt[y]=max(cnt[y],len);
        }
    }
    ll query(int st){
        ll ret=0;
        static int q[MAX_N],rd[MAX_N]; int h=1,t=0;
        for(int i=st;i<=top;++i) rd[i]=0;
        for(int i=st;i<=top;++i) ++rd[tree[i].fail];
        for(int i=st;i<=top;++i) rd[i]?0:q[++t]=i;
        while(h<=t){
            int x=q[h++],y=tree[x].fail;
            cnt[y]=max(cnt[y],cnt[x]);
            --rd[y];
            if(rd[y]==0) q[++t]=y;
        }
        for(int i=st;i<=top;++i){
            ret+=tree[i].max-tree[tree[i].fail].max;
            if(i>st&&cnt[i]>0) 
                ret-=max(min(tree[i].max,cnt[i])-tree[tree[i].fail].max,0);
        }
        return ret;
    }
    void init(char* s){
        for(int i=1;i<=top;++i)
            TREE::add_edge(tree[i].fail,i);
        TREE::dfs(1);
        int len=strlen(s),x=1;
        for(int i=0;i<len;++i){
            x=tree[x].son[s[i]-'a'];
            SEG::change(rt[i],rt[i+1],1,top1,TREE::dfn[x],i+1);
        }
    }
}
char s[MAX_N],t[MAX_N];
int getint(){
    int ret=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        ret=ret*10+c-'0';
    return ret;
}
int main(){
    memset(TREE::head,-1,sizeof(TREE::head));
    scanf("%s",s),n=strlen(s);
    for(int i=0;i<n;++i) top1=SAM::insert(1,top1,s[i]-'a');
    top1=SAM::top; 
    SAM::init(s);
    SAM::top=top1+1;
    SAM::init(top1+1);
    int q=getint();
    while(q--){
        int l,r; scanf("%s",t);
        l=getint(),r=getint();
        int n=strlen(t),last=top1+1;
        SAM::top=top1+1,SAM::init(last);
        for(int i=0;i<n;++i) last=SAM::insert(top1+1,last,t[i]-'a');
        SAM::solve(1,top1+1,l,r,t);
        printf("%lld\n",SAM::query(top1+1));
    }
    return 0;
}

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

JavaScript面向对象编程指南

斯托扬 / 凌杰 / 人民邮电出版社 / 2013-3 / 59.00元

《JavaScript面向对象编程指南》内容包括：JavaScript作为一门浏览器语言的核心思想；面向对象编程的基础知识及其在JavaScript中的运用；数据类型、操作符以及流程控制语句；函数、闭包、对象和原型等概念，以代码重用为目的的继承模式；BOM、DOM、浏览器事件、AJAX和JSON；如何实现JavaScript中缺失的面向对象特性，如对象的私有成员与私有方法；如何应用适当的编程模式，......一起来看看《JavaScript面向对象编程指南》这本书的介绍吧!

码农工具