BZOJ3172 [Tjoi2013]单词 AC自动机+fail树

yts1999 posted @ 2014年8月22日 09:48 in AC自动机 with tags bzoj AC自动机 , 2177 阅读

AC自动机+fail树

参考代码:

/**************************************************************
    Problem: 3172
    User: yts1999
    Language: C++
    Result: Accepted
    Time:488 ms
    Memory:129032 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
 
struct Treenode {
    Treenode *fail,*next[26];
    int count,num;
    int s;
};
 
Treenode *root;
char a[1000100];
Treenode *pl[1000];
int tot = 0;
 
void insert(int k) {
    Treenode *p = root;
    int len = strlen(a);
    for (int i = 0; i < len; i++) {
        if (p->next[a[i] - 'a'] == NULL) {
            p->next[a[i] - 'a'] = new Treenode;
            p->next[a[i] - 'a']->count = 0;
            p->next[a[i] - 'a']->fail = NULL;
            for (int j = 0; j < 26; j++)
                p->next[a[i] - 'a']->next[j] = NULL;
            p->next[a[i] - 'a']->num = tot++;
            p->next[a[i] - 'a']->s = 0;
        }
        if (i == len - 1) {
            p->next[a[i] - 'a']->count = k;
            pl[k] = p->next[a[i] - 'a'];
        }
        p = p->next[a[i] - 'a'];
        p->s++;
    }
}
 
struct Edge {
    Treenode *y;
    Edge *next;
};
 
Edge *b[26000100];
 
void addedge(Treenode *x,Treenode *y) {
    Edge *k = new Edge;
    k->y = y;
    k->next = b[x->num];
    b[x->num] = k;
}
 
void build_fail() {
    queue<Treenode*> q;
    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]);
                }
            }
    }
}
 
void dfs(Treenode *fa) {
    for (Edge *p = b[fa->num]; p != NULL; p = p->next) {
        dfs(p->y);
        fa->s += p->y->s;
    }
}
 
int main() {
    root = new Treenode;
    root->count = 0;
    root->fail = NULL;
    root->s = 0;
    for (int i = 0; i < 26; i++)
        root->next[i] = NULL;
    root->num = tot++;
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s",a);
        insert(i);
    }
    build_fail();
    dfs(root);
    for (int i = 0; i < n; i++)
        printf("%d\n",pl[i]->s);
    return 0;
}

登录 *


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