2013-team4/code/ac-automation

从 Trac 迁移的文章

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

原文章内容如下：

{{{
AC自动机
要跟据题意修改 idx() 和 print() 这两个函数
idx() 为字符到 int 的映射, print() 为找到模板串后调用的函数
!!注意要在使用 find() 前先使用 get_fail()
!!注意插入相同的模式串的时候会被覆盖
}}}
{{{
创建
AC ac;
插入一个长度为 len 的字符串 str, 附加信息为 value
ac.insert(str, len, value);
调用 find 函数前要调用 get_fail
ac.get_fail();
查找, 文本串 s 长度为 len
ac.find(s, len);
}}}
{{{
typedef int DATA;
const int MAXL = 50007, SIGMA = 26;

struct AC{
    int cnt, ch[MAXL][SIGMA], fail[MAXL], last[MAXL];
    bool end[MAXL];
    DATA val[MAXL];
    AC(){
        clear();
    }
    void clear(){
        cnt = 1; 
        end[0] = false;
        memset(ch[0], 0, sizeof(ch[0]));
    }
    int idx(char c){
        return c - 'A';
    }
    void insert(const char *s, int n, DATA value){
        int now = 0;
        for(int c, i = 0; i < n; i++, now = ch[now][c]){
            c = idx(s[i]);
            if(ch[now][c] == 0){
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                end[cnt] = false;
                ch[now][c] = cnt++;
            }
        }
        end[now] = true; val[now] = value;
    }
    void get_fail(){
        queue<int> q;
        fail[0] = 0;
        for(int c = 0; c < SIGMA; c++){
            int u = ch[0][c];
            if(u != 0){
                fail[u] = last[u] = 0;
                q.push(u);
            }
        }
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int c = 0; c < SIGMA; c++){
                int &y = ch[x][c];
                if(y == 0) y = ch[fail[x]][c];
                else{
                    fail[y] = ch[fail[x]][c];
                    last[y] = end[fail[y]] ? fail[y] : last[fail[y]];
                    q.push(y);
                }
            }
        }
    }
    void print(int pos, int x){
        cout << "find " << val[x] << " end at " << pos << endl;
        if(last[x] != 0) print(pos, last[x]);
    }
    void find(const char *s, int n){
        int now = 0;
        for(int i = 0; i < n; i++){
            int c = idx(s[i]);
            now = ch[now][c];
            if(end[now]) print(i, now);
            else if(last[now] != 0) print(i, last[now]);
        }
    }
};
}}}

AC自动机
要跟据题意修改 idx() 和 print() 这两个函数
idx() 为字符到 int 的映射, print() 为找到模板串后调用的函数
!!注意要在使用 find() 前先使用 get_fail()
!!注意插入相同的模式串的时候会被覆盖

创建
AC ac;
插入一个长度为 len 的字符串 str, 附加信息为 value
ac.insert(str, len, value);
调用 find 函数前要调用 get_fail
ac.get_fail();
查找, 文本串 s 长度为 len
ac.find(s, len);

typedef int DATA;
const int MAXL = 50007, SIGMA = 26;
struct AC{
    int cnt, ch[MAXL][SIGMA], fail[MAXL], last[MAXL];
    bool end[MAXL];
    DATA val[MAXL];
    AC(){
        clear();
    }
    void clear(){
        cnt = 1; 
        end[0] = false;
        memset(ch[0], 0, sizeof(ch[0]));
    }
    int idx(char c){
        return c - 'A';
    }
    void insert(const char *s, int n, DATA value){
        int now = 0;
        for(int c, i = 0; i < n; i++, now = ch[now][c]){
            c = idx(s[i]);
            if(ch[now][c] == 0){
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                end[cnt] = false;
                ch[now][c] = cnt++;
            }
        }
        end[now] = true; val[now] = value;
    }
    void get_fail(){
        queue<int> q;
        fail[0] = 0;
        for(int c = 0; c < SIGMA; c++){
            int u = ch[0][c];
            if(u != 0){
                fail[u] = last[u] = 0;
                q.push(u);
            }
        }
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int c = 0; c < SIGMA; c++){
                int &y = ch[x][c];
                if(y == 0) y = ch[fail[x]][c];
                else{
                    fail[y] = ch[fail[x]][c];
                    last[y] = end[fail[y]] ? fail[y] : last[fail[y]];
                    q.push(y);
                }
            }
        }
    }
    void print(int pos, int x){
        cout << "find " << val[x] << " end at " << pos << endl;
        if(last[x] != 0) print(pos, last[x]);
    }
    void find(const char *s, int n){
        int now = 0;
        for(int i = 0; i < n; i++){
            int c = idx(s[i]);
            now = ch[now][c];
            if(end[now]) print(i, now);
            else if(last[now] != 0) print(i, last[now]);
        }
    }
};