AC自动机

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== Darksun_140305 === 

{{{
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MaxC=62; /* 最大字符种数 */
struct Trie_Node{
    int next[MaxC],last,fail,val;
} ept;  /* last为后缀链接,fail为失配边,val为节点值 */
        /* val==0表示该点不是模板串的结尾 */
        /* val!=0表示该点是模板串的结尾,且该模板串有val个后缀是模板串 */
typedef vector <Trie_Node> AC;
AC A;

int idx(char c){
    if ('0'<=c && c<='9') return c-'0';
    if ('a'<=c && c<='z') return c-'a'+10;
    if ('A'<=c && c<='Z') return c-'A'+36;
}
void insert(char *s, AC &A){
    int len=strlen(s);
    int i,j,u=0;
    for (i=0; i<len; i++){
        int v=idx(s[i]);
        if (!A[u].next[v]){
            A.push_back(ept);
            A[u].next[v]=A.size()-1;
        }
        u=A[u].next[v];
    }
    A[u].val=1;
}    /* 建立模板的Trie */
void getFail(AC &A){
    queue <int> Q;
    for (int c=0; c<MaxC; c++){
        int u=A[0].next[c];
        if (u) Q.push(u);
    }
    while (!Q.empty()){
        int u=Q.front(); Q.pop();
        for (int c=0; c<MaxC; c++){
            int v=A[u].next[c];
            if (!v){ A[u].next[c]=A[A[u].fail].next[c]; continue; }
            /* 如果u点没有c边，则直接变成失配边 */
            Q.push(v);
            int t=A[u].fail;
            while (t && !A[t].next[c]) t=A[t].fail;
            /* 沿着失配边走，直到找到等于当前串后缀的串，或者回0点 */
            int tmp=A[t].next[c];
            A[v].fail=tmp;
            A[v].last=A[tmp].val? tmp: A[tmp].last;
            if (A[v].val) A[v].val+=A[A[v].last].val;
        }
    }
}    /* BFS建立自动机的失配边 */

const int MN=1e6+7;
int t[MN];

void calc(int u){
    if (u){ t[u]++; calc(A[u].last); }
}
void match(char *s){
    int len=strlen(s);
    int i,j=0;
    for (i=0; i<len; i++){
        int c=idx(s[i]);
        j=A[j].next[c];
        if (A[j].val) calc(j);
        else if (A[j].last) calc(A[j].last);
    }
}    /* 匹配文本串，计算每个模板的出现次数 */

int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0) break;
        A.clear(); A.push_back(ept);
        memset(t,0,sizeof(t));
        char ss[MN];
        int i,j,k;
        for (i=1; i<=n; i++){
            scanf("%s",ss);
            insert(ss,A);
        }                 /* 读入模板 */
        scanf("%s",ss);   /* 读入文本 */
        getFail(A);
        match(ss);
        int maxt=0;
        for (i=1; i<A.size(); i++) maxt=max(maxt,t[i]);
        printf("%d\n",maxt);    /* 输出出现次数最高的模板的出现次数 */
    }
    return 0;
}
}}}

=== AIdancer ===
{{{
struct node {
    int ct;
    node *pre, *next[26];
    void init() {
        ct = 0;
        pre = 0;
        memset(next, 0, sizeof(next));
    }
};

int cnt; //节点总数
node *root, trie[500010];

node *queue[500010];

void insertStr(node *root, char *str) {
    int index, len = strlen(str);
    for(int i = 0; i < len; i++) {
        index = str[i]-'a';
        if(root->next[index] == 0) {
            root->next[index] = &trie[++cnt];
            root->next[index]->init();
        }
        root = root->next[index];
    }
    root->ct++;
}

void buildAC() {
    int head, tail;
    node *u, tmp;
    queue[0] = root;
    root->pre = root;
    head = tail = 0;
    while(head <= tail) {
        u = queue[head++];
        for(int i = 0; i < 26; i++) {
            if(u->next[i] == 0) {
                if(u == root)  u->next[i] = root;
                else  u->next[i] = u->pre->next[i];
            }
            else {
                if(u == root)  u->next[i]->pre = root;
                else  u->next[i]->pre = u->pre->next[i];
                queue[++tail] = u->next[i];
            }
        }
    }
}
}}}

Darksun_140305

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MaxC=62; /* 最大字符种数 */
struct Trie_Node{
    int next[MaxC],last,fail,val;
} ept;  /* last为后缀链接,fail为失配边,val为节点值 */
        /* val==0表示该点不是模板串的结尾 */
        /* val!=0表示该点是模板串的结尾,且该模板串有val个后缀是模板串 */
typedef vector <Trie_Node> AC;
AC A;
int idx(char c){
    if ('0'<=c && c<='9') return c-'0';
    if ('a'<=c && c<='z') return c-'a'+10;
    if ('A'<=c && c<='Z') return c-'A'+36;
}
void insert(char *s, AC &A){
    int len=strlen(s);
    int i,j,u=0;
    for (i=0; i<len; i++){
        int v=idx(s[i]);
        if (!A[u].next[v]){
            A.push_back(ept);
            A[u].next[v]=A.size()-1;
        }
        u=A[u].next[v];
    }
    A[u].val=1;
}    /* 建立模板的Trie */
void getFail(AC &A){
    queue <int> Q;
    for (int c=0; c<MaxC; c++){
        int u=A[0].next[c];
        if (u) Q.push(u);
    }
    while (!Q.empty()){
        int u=Q.front(); Q.pop();
        for (int c=0; c<MaxC; c++){
            int v=A[u].next[c];
            if (!v){ A[u].next[c]=A[A[u].fail].next[c]; continue; }
            /* 如果u点没有c边，则直接变成失配边 */
            Q.push(v);
            int t=A[u].fail;
            while (t && !A[t].next[c]) t=A[t].fail;
            /* 沿着失配边走，直到找到等于当前串后缀的串，或者回0点 */
            int tmp=A[t].next[c];
            A[v].fail=tmp;
            A[v].last=A[tmp].val? tmp: A[tmp].last;
            if (A[v].val) A[v].val+=A[A[v].last].val;
        }
    }
}    /* BFS建立自动机的失配边 */
const int MN=1e6+7;
int t[MN];
void calc(int u){
    if (u){ t[u]++; calc(A[u].last); }
}
void match(char *s){
    int len=strlen(s);
    int i,j=0;
    for (i=0; i<len; i++){
        int c=idx(s[i]);
        j=A[j].next[c];
        if (A[j].val) calc(j);
        else if (A[j].last) calc(A[j].last);
    }
}    /* 匹配文本串，计算每个模板的出现次数 */
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0) break;
        A.clear(); A.push_back(ept);
        memset(t,0,sizeof(t));
        char ss[MN];
        int i,j,k;
        for (i=1; i<=n; i++){
            scanf("%s",ss);
            insert(ss,A);
        }                 /* 读入模板 */
        scanf("%s",ss);   /* 读入文本 */
        getFail(A);
        match(ss);
        int maxt=0;
        for (i=1; i<A.size(); i++) maxt=max(maxt,t[i]);
        printf("%d\n",maxt);    /* 输出出现次数最高的模板的出现次数 */
    }
    return 0;
}

AIdancer

struct node {
    int ct;
    node *pre, *next[26];
    void init() {
        ct = 0;
        pre = 0;
        memset(next, 0, sizeof(next));
    }
};
int cnt; //节点总数
node *root, trie[500010];
node *queue[500010];
void insertStr(node *root, char *str) {
    int index, len = strlen(str);
    for(int i = 0; i < len; i++) {
        index = str[i]-'a';
        if(root->next[index] == 0) {
            root->next[index] = &trie[++cnt];
            root->next[index]->init();
        }
        root = root->next[index];
    }
    root->ct++;
}
void buildAC() {
    int head, tail;
    node *u, tmp;
    queue[0] = root;
    root->pre = root;
    head = tail = 0;
    while(head <= tail) {
        u = queue[head++];
        for(int i = 0; i < 26; i++) {
            if(u->next[i] == 0) {
                if(u == root)  u->next[i] = root;
                else  u->next[i] = u->pre->next[i];
            }
            else {
                if(u == root)  u->next[i]->pre = root;
                else  u->next[i]->pre = u->pre->next[i];
                queue[++tail] = u->next[i];
            }
        }
    }
}