BZOJ3172&&lg3966 TJOI单词(广义后缀自动机)

题面

自己找去

HINT

给出多个文本串，让你查找每个文本串一共出现了多少次，广义后缀自动机建出parent tree然后上推就好了鸭，感觉代码也没有什么细节，写就完事了。

#include<bits/stdc++.h>

#include<set>

using namespace std;

const int maxn=200010;

inline int read(){

    int w=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-') f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        w=(w<<3)+(w<<1)+ch-48;

        ch=getchar();

    }

    return w*f;

}

int n,m;

bool debug;

set<int> s[maxn];

set<int>::iterator it;

int size[2000010];

struct SUFFIXAUTOMATON{

    struct Node{

        int len,fa;

        map<int,int> ch;

    }node[2000010];

    int lst,tot,root;

    inline void init(){

        lst=tot=root=1;return;

    }

    inline void extend(int now){

        int p=lst;tot++;lst=tot;int np=tot;

        node[np].len=node[p].len+1;size[np]=1;

        while(p&&!node[p].ch[now]){

            node[p].ch[now]=np;

            p=node[p].fa;

        }

        if(!p) node[np].fa=1;

        else{

            int q=node[p].ch[now];

            if(node[q].len==node[p].len+1){

                node[np].fa=q;

            }

            else{

                int nq=++tot;node[nq]=node[q];

                node[nq].len=node[p].len+1;

                node[q].fa=nq;node[np].fa=nq;

                while(p&&node[p].ch[now]==q){

                    node[p].ch[now]=nq;

                    p=node[p].fa;

                }

            }

        }

    }

}SAM;

string ch[210];

int cnt,head[2000010];

struct Edge{

    int from,to,next;

}edge[5000010];

inline void addedge(int u,int v){

    cnt++;

    edge[cnt].from=u;

    edge[cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

inline void dfs(int u){

    for(int i=head[u];i;i=edge[i].next){

        int v=edge[i].to;dfs(v);

        size[u]+=size[v];

    }

    return;

}

int main(){

    n=read();SAM.init();

    for(int i=1;i<=n;i++){

        cin>>ch[i];int len=ch[i].length();

        for(int j=0;j<len;j++){

            SAM.extend(ch[i][j]-'a'+1);

        }

        SAM.lst=1;

    }

    for(int i=2;i<=SAM.tot;i++){

        addedge(SAM.node[i].fa,i);

    }

    dfs(1);

    for(int i=1;i<=n;i++){

        int u=1;int len=ch[i].length();

        for(int j=0;j<len;j++){

            u=SAM.node[u].ch[ch[i][j]-'a'+1];

        }

        printf("%d\n",size[u]);

    }

    return 0;

}

巴特西

BZOJ3172&&lg3966 TJOI单词(广义后缀自动机)

BZOJ3172&&lg3966 TJOI单词(广义后缀自动机)

题面

HINT

最新文章

热门文章