BZOJ2434 [Noi2011]阿狸的打字机 AC自动机+fail树+dfs序+树状数组

yts1999 posted @ 2014年8月22日 10:03 in AC自动机 with tags 树状数组 bzoj AC自动机 , 1625 阅读

AC自动机+fail树+dfs序+树状数组

建一个AC自动机,然后在上面倒着建出fail树,求出dfs序,再用树状数组搞一搞就好了。。。

参考代码:

/**************************************************************
    Problem: 2434
    User: yts1999
    Language: C++
    Result: Accepted
    Time:904 ms
    Memory:15284 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
 
struct Treenode {
    Treenode *fail,*next[26],*fa;
    int tot;
    int num;
    int number;
};
 
Treenode *root;
char init[100100];
int tot;
Treenode *place[100100];
queue<Treenode*> q;
Treenode *dfsx[200000];
int totd;
int numtot = 0;
 
void insert() {
    int len = strlen(init);
    Treenode *p = root;
    for (int i = 0; i < len; i++)
        if (init[i] >= 'a' && init[i] <= 'z') {
            int k = init[i] - 'a';
            if (p->next[k] == NULL) {
                p->next[k] = new Treenode;
                p->next[k]->fail = NULL;
                p->next[k]->tot = 0;
                p->next[k]->fa = p;
                p->next[k]->num = 0;
                p->next[k]->number = ++numtot;
                for (int i = 0; i < 26; i++)
                    p->next[k]->next[i] = NULL;
                p->next[k]->fa = p;
            }
            p = p->next[k];
        }
        else
            switch (init[i]) {
                case 'P':
                    place[++tot] = p;
                    p->num = tot;
                    break;
                case 'B':
                    p = p->fa;
                    break;
            }
}
 
struct Edge {
    Treenode *y;
    Edge *next;
};
 
Edge *b[100010];
 
void addedge(Treenode *x,Treenode *y) {
    Edge *k = new Edge;
    k->y = y;
    k->next = b[x->number];
    b[x->number] = k;
}
 
void build_fail() {
    for (int i = 0; i < 26; i++)
        if (root->next[i] != NULL) {
            root->next[i]->fail = root;
            addedge(root,root->next[i]);
            q.push(root->next[i]);
        }
    for (;! q.empty();) {
        Treenode *p = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
            if (p->next[i] != NULL) {
                q.push(p->next[i]);
                Treenode *temp = p->fail;
                for (; temp != NULL && temp != root && temp->next[i] == NULL;)
                    temp = temp->fail;
                if (temp->next[i] != NULL) {
                    p->next[i]->fail = temp->next[i];
                    addedge(temp->next[i],p->next[i]);
                }
                else {
                    p->next[i]->fail = root;
                    addedge(root,p->next[i]);
                }
            }
    }
}
 
int pl[100100][2];
int pla[100100];
 
void dfs(Treenode *fa) {
    if (fa != root) {
        dfsx[++totd] = fa;
        pl[fa->num][0] = totd;
        pla[fa->number] = totd;
    }
    for (Edge *i = b[fa->number]; i != NULL; i = i->next)
        dfs(i->y);
    if (fa != root) {
        dfsx[++totd] = fa;
        pl[fa->num][1] = totd;
    }
}
 
struct Ask {
    int x,y,ord,ans;
};
 
Ask qu[100100];
 
bool cmp(Ask a,Ask b) {
    return a.y < b.y;
}
 
bool cmp1(Ask a,Ask b) {
    return a.ord < b.ord;
}
 
int c[200000];
int dfsa[200000];
 
int lowbit(int x) {
    return x & -x;
}
 
void modify(int a,int d) {
    int k = d - dfsa[a];
    dfsa[a] = d;
    for (; a <= totd;) {
        c[a] += k;
        a += lowbit(a);
    }
}
 
int getsum(int a) {
    int ans = 0;
    for (; a > 0;) {
        ans += c[a];
        a -= lowbit(a);
    }
    return ans;
}
 
int main() {
    root = new Treenode;
    root->fail = NULL;
    root->fa = NULL;
    root->tot = 0;
    root->num = 0;
    root->number = 0;
    for (int i = 0; i < 26; i++)
        root->next[i] = NULL;
    scanf("%s",init);
    tot = 0;
    insert();
    build_fail();
    totd = 0;
    dfs(root);
    int m;
    scanf("%d",&m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d",&qu[i].x,&qu[i].y);
        qu[i].ord = i;
    }
    sort(qu,qu + m,cmp);
    Treenode *p = root;
    int leninit = strlen(init);
    int nowy = 0;
    int i = 0;
    for (int nowin = 0; nowin < leninit; nowin++)
        if (init[nowin] >= 'a' && init[nowin] <= 'z') {
            p = p->next[init[nowin] - 'a'];
            modify(pla[p->number],1);
        }
        else
            switch (init[nowin]) {
                case 'P':
                    nowy++;
                    for (;qu[i].y == nowy; i++)
                        qu[i].ans = getsum(pl[qu[i].x][1]) - getsum(pl[qu[i].x][0] - 1);
                    break;
                case 'B':
                    modify(pla[p->number],0);
                    p = p->fa;
                    break;
            }
    sort(qu,qu + m,cmp1);
    for (int i = 0; i < m; i++)
        printf("%d\n",qu[i].ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter