[NOI2011]阿狸的打字机

Luogu 2414

bzoj 2434

思路

从点$v$开始,沿着fail指针跳,所经过的点为终点的串都是$v$为终点的串的子串。

所以暴力做法就是从所给$y$串的结尾处向上跳,在每个点都沿着fail指针跳,看是否出现$x$串的结尾节点,若出现就累加一下。

优化暴力做法,将fail边反着建一下,就得到一棵fail树。统计方法可以变为$x$串结尾节点的子树中,出现了多少个$y$串中的节点。

所以我们可以离线一下,将询问按$y$排序,将串$s$中的元素依次加入Trie树,使得当前树状数组维护的dfs序序列中,$y$的每个节点权值都是$1$,记录每个$y$相同的询问的答案,最后一起输出即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

struct Data{
    int x, y, id, ans;
}a[100010];

class AC{
private:
    class BIT{
        private:
            int a[100010];
            int lowbit(int x){return (x&(-x));}
        public:
            BIT(){
                memset(a, 0, sizeof(a));
            }
            void add(int x, int y){
                for(int i=x; i<=100000; i+=lowbit(i))
                    a[i]+=y;
            }
            int sum(int x){
                int ans=0;
                for(int i=x; i; i-=lowbit(i))
                    ans+=a[i];
                return ans;
            }
    };
    int cnt;
    struct Edge;
    struct Node{
      	Edge *head;
        Node *c[26], *fa, *fail;
        int siz, dfn;
        Node (Node *fa) : siz(0), dfn(0), head(NULL), 
            fa(fa), fail(NULL){
            for(int i=0; i<26; i++)
                c[i]=NULL;
        }
    }*root, *ed[100010];
    
    struct Edge{
    	Node *to;
    	Edge *ne;
    	Edge(Node *x, Node *y) : to(y), ne(x->head){}
    };
    
    void dfs_fail(Node *x, Node *fa){
    	x->dfn=++cnt;
    	x->siz=1;
    	for(Edge *i=x->head; i; i=i->ne) if(i->to!=fa){
    	    dfs_fail(i->to, x);
    	    x->siz+=i->to->siz;
    	}
    }

public:
    AC() : cnt(0){
        root=new Node(NULL);
    }

    void insert(char *s){
        int len=strlen(s+1);
        Node *v=root;
        for(int i=1; i<=len; i++){
            if(s[i]=='P')		ed[++cnt]=v;
            else if(s[i]=='B')	v=v->fa;
            else{
                if(!v->c[s[i]-'a'])
                    v->c[s[i]-'a']=new Node(v);
                v=v->c[s[i]-'a'];
            }
        }
    }
    
    void build(){
        std::queue<Node *>q;
        root->fail=root;
        q.push(root);
        while(!q.empty()){
            Node *v=q.front();
            q.pop();
            for(int i=0; i<26; i++){
                if(!v->c[i]){
                    if(v==root)	v->c[i]=root;
                    else	v->c[i]=v->fail->c[i];
                    continue;
                }
                if(v!=root && v->fail->c[i])
                    v->c[i]->fail=v->fail->c[i];
                else
                    v->c[i]->fail=root;
                v->c[i]->fail->head=new Edge(v->c[i]->fail, v->c[i]);
                q.push(v->c[i]);
            }
        }
    }
    
    void dfs_fail(){
    	cnt=0;
    	dfs_fail(root, NULL);
    }
    
    void work(char *s){
    	int len=strlen(s+1), now=1;cnt=0;
    	BIT *B=new BIT;
    	Node *v=root;
    	for(int i=1; i<=len; i++){
    	    if(s[i]=='B'){
    		B->add(v->dfn, -1);
    		v=v->fa;
    	    }else if(s[i]=='P'){
    		cnt++;
    		while(a[now].y==cnt){
    	            Node *vv=ed[a[now].x];
    		    a[now].ans=B->sum(vv->dfn+vv->siz-1)-B->sum(vv->dfn-1);
    		    now++;
    		}
    		if(a[now].y==-1)	return;
    	    }else{
                v=v->c[s[i]-'a'];
                B->add(v->dfn, 1);
            }
    	}
    }
};

bool cmp1(const Data &_, const Data &__){return _.y<__.y;}

bool cmp2(const Data &_, const Data &__){return _.id<__.id;}

int main(){
    int m, x, y;
    char s[100010];
    AC *T=new AC;
    scanf("%s", s+1);
    T->insert(s);
    T->build();
    scanf("%d", &m);
   	for(int i=1; i<=m; i++){
        scanf("%d%d", &a[i].x, &a[i].y);
     	a[i].id=i;   
    }
    std::sort(a+1, a+m+1, cmp1);
    a[m+1].y=-1;
    T->dfs_fail();	T->work(s);
    std::sort(a+1, a+m+1, cmp2);
    for(int i=1; i<=m; i++)	
        printf("%d\n", a[i].ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注