HYSBZ - 2434 && Codeforces 163 E【AC自动机+dfn序列】

太过爱你忘了你带给我的痛 2022-08-04 12:37 10阅读 0赞

两道题都是建立逆fail树，进行区间操作。

[阿里的打字机][Link 1]

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAC=26;
    const int MAXN=100010;
    
    struct BIT
    {
        int c[MAXN];
        int size;
        void init(int tn)
        {
            CLR(c,0);
            size=tn;
        }
    
        void add(int sour,int value)
        {
            for(int i=sour; i<=size; i+=lowbit(i))
                c[i]+=value;
        }
        int query(int sour)
        {
            int ret=0;
            for(int i=sour; i; i-=lowbit(i))
                ret+=c[i];
            return ret;
        }
    } T;
    
    int dfn[MAXN], rdfn[MAXN]; //子树左界，右界
    int timestamp;
    
    struct TREE
    {
        struct EDGE
        {
            int v,next;
        } e[MAXN];
        int head[MAXN];
        int tot;
        void init()
        {
            CLR(head,-1);
            tot=0;
        }
        void addedge(int tu,int tv)
        {
            e[tot].v=tv;
            e[tot].next=head[tu];
            head[tu]=tot++;
        }
        void dfs(int u)
        {
            dfn[u]=++timestamp;
            for(int i=head[u]; ~i; i=e[i].next)
                dfs(e[i].v);
            rdfn[u]=timestamp;
        }
    };
    
    TREE tree;  //fail逆向指针树
    
    vector<pii> query[MAXN];  //询问
    int words;
    int hash[MAXN];                       //串到trie图节点的映射
    int ans[MAXN];                        //答案
    bool vis[MAXN];                       //防止重复处理询问
    
    struct AC
    {
        int ch[MAXN][MAC],f[MAXN],size;
        vector<int> end[MAXN];  //记录节点对应的串
        int fa[MAXN];
        inline int idx(char ch)
        {
            return ch-'a';
        }
        void init()
        {
            size=0;f[0]=0;
            newnode(0);
        }
    
        int newnode(int pre)
        {
            CLR(ch[size],0);
            fa[size]=pre;
            end[size].clear();
            return size++;
        }
    
        void insert(char *S)
        {
            int u=0,p;
            for(char *sp=S; *sp; sp++)
                if(*sp=='P')
                {
                    hash[++words]=u;
                    query[words].clear();
                    end[u].pb(words);
                }
                else if(*sp=='B')
                    u=fa[u];
                else
                {
                    p=idx(*sp);
                    if(!ch[u][p])
                    {
                        ch[u][p]=newnode(u);
                    }
                    u=ch[u][p];
                }
        }
    
        int que[MAXN],front,back;
        void build()
        {
            front=back=0;
            int u,cur,id;
            for(int i=0; i<MAC; i++)
                if(ch[0][i])
                {
                    que[back++]=ch[0][i];
                    f[ch[0][i]]=0;
                }
            while(front<back)
            {
                cur=que[front++];
                for(int i=0; i<MAC; i++)
                {
                    u=ch[cur][i];
                    if(u)
                    {
                        que[back++]=u;
                        f[u]=ch[f[cur]][i];
                    }
                    else
                        ch[cur][i]=ch[f[cur]][i];
                }
            }
        }
    
        void solve(char *S)
        {
            CLR(vis,0);
            tree.init();
            for(int i=1; i<size; i++)
                tree.addedge(f[i],i);
            timestamp=0;
            tree.dfs(0);
            T.init(size+5);
            int u=0;
            for(char *sp=S;*sp;sp++)
                if(*sp=='P')
                {
                    if(vis[u])
                        continue;
                    vis[u]=true;
                    int ts1=end[u].size();
                    for(int i=0; i<ts1; i++)
                    {
                        int y=end[u][i];
                        int ts2=query[y].size();
                        for(int j=0; j<ts2; j++)
                        {
                            int x=query[y][j].first,id=query[y][j].second;
                            ans[id]=T.query(rdfn[hash[x]])-T.query(dfn[hash[x]]-1);
                        }
                    }
                }
                else if(*sp=='B')
                {
                    T.add(dfn[u],-1);
                    u=fa[u];
                }
                else
                {
                    u=ch[u][idx(*sp)];
                    T.add(dfn[u], 1);
                }
        }
    
    } ac;
    
    
    char str[MAXN];
    
    int main()
    {
        while(~scanf("%s",str))
        {
            ac.init();
            words=0;
            ac.insert(str);
            int n;
            scanf("%d",&n);
            int x,y;
            for(int i=1; i<=n; i++)
            {
                scanf("%d%d",&x,&y);
                query[y].pb(mp(x,i));
            }
            ac.build();
            ac.solve(str);
            for(int i=1; i<=n; i++)
                printf("%d\n", ans[i]);
        }
        return 0;
    }

[e-Government][]

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAC=26;
    const int MAXN=1000010;
    int n,m;
    
    struct BIT
    {
        int c[MAXN],size;
        void init(int tn)
        {
            CLR(c,0);size=tn;
        }   
        void add(int i,int val)
        {
            for(;i<size;i+=lowbit(i))
                c[i]+=val;
        }
        int getsum(int i)
        {
            int sum=0;
            for(;i;i-=lowbit(i))
                sum+=c[i];
            return sum;
        }
    }T;
    
    int dfn[MAXN],rdfn[MAXN];
    int timestamp;
    
    struct Tree
    {
        struct Edge
        {
            int to,next;
        }e[MAXN];
        int head[MAXN],tot;
        void init()
        {
            CLR(head,-1);tot=1;
        }
        void addedge(int u,int v)
        {
            e[tot].to=v;e[tot].next=head[u];
            head[u]=tot++;
        }
        void dfs(int u)
        {
            dfn[u]=++timestamp;
            for(int i=head[u];~i;i=e[i].next)
                dfs(e[i].to);
            rdfn[u]=timestamp;
        }
    }tree;
    
    struct AC
    {
        int ch[MAXN][MAC],f[MAXN],size;
        int end[MAXN];
        int pos[MAXN];
        void init()
        {
            size=0;f[0]=0;
            newnode(0);
        }
    
        int newnode(int pre)
        {
            CLR(ch[size],0);
            end[size]=pos[size]=0;
            return size++;
        }
    
        void insert(char *S,int id)
        {
            int u=0,x;
            for(char *sp=S;*sp;sp++)
            {
                x=*sp-'a';
                if(!ch[u][x])
                {
                    ch[u][x]=newnode(u);
                }
                u=ch[u][x];
            }
            end[u]=1;
            pos[id]=u;
        }
        int que[MAXN],front,back;
        void build()
        {
            int u,cur;
            front=back=0;
            for(int i=0;i<MAC;i++)
                if(ch[0][i])
                {
                    que[back++]=ch[0][i];
                    f[ch[0][i]]=0;
                }
            while(front<back)
            {
                cur=que[front++];
                for(int i=0;i<MAC;i++)
                {
                    u=ch[cur][i];
                    if(u)
                    {
                        que[back++]=u;
                        f[u]=ch[f[cur]][i];
                        end[u]+=end[f[u]]; 
                    }
                    else
                        ch[cur][i] = ch[f[cur]][i];
                }
            } 
            tree.init();
            T.init(size+10);
            for(int i=1;i<size;i++)
                tree.addedge(f[i],i);
            timestamp=0;
            tree.dfs(0);
            for(int i=0;i<size;i++)
            {
                T.add(dfn[i],end[i]);
                T.add(dfn[i]+1,-end[i]);
            }
        }
        int query(char *S)
        {
            int u=0,ans=0,x;
            for(char *sp=S;*sp;sp++)
            {
                x=*sp-'a';
                u=ch[u][x];
                if(end[u])
                    ans+=T.getsum(dfn[u]);
            }
            return ans;
        }
    } ac;
    
    char str[MAXN],op[MAXN];
    bool has[MAXN];
    
    int main()
    {
        ac.init();
        scanf("%d %d",&m,&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str);
            ac.insert(str,i);
            has[i]=true;    
        }
        ac.build();
        for(int i=1,temp;i<=m;i++)
        {
            scanf("%s",op);
            if(op[0]=='?')
            {
                printf("%d\n",ac.query(op+1));
            }
            else if(op[0]=='-')
            {
                sscanf(op+1,"%d",&temp);
                if(has[temp])
                {
                    has[temp]=false;  
                    T.add(dfn[ac.pos[temp]],-1);  
                    T.add(rdfn[ac.pos[temp]]+1,1); 
                }
            }
            else
            {
                sscanf(op+1,"%d",&temp);
                if(!has[temp])
                {
                    has[temp]=true;  
                    T.add(dfn[ac.pos[temp]],1);  
                    T.add(rdfn[ac.pos[temp]]+1,-1); 
                }
            }
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/huzecong/article/details/7769988
[e-Government]: http://blog.csdn.net/u013368721/article/details/40653313