2013-team6/automaton

从 Trac 迁移的文章

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

原文章内容如下：

{{{
初始化

ac.init()

插入

ac.insert(str)

找fail函数

ac.make()

匹配

ac.find()

index记状态

end记录有几个串结束
}}}
{{{

#include <iostream>
#include <queue>

using namespace std;

class Automaton{
    public:
    static const int MAXN=500010;
    static const int LEAF=28;
    int trie[MAXN][LEAF],fail[MAXN];
    int end[MAXN];
    int n;

    void clear(int v){
        memset(trie[v],0,sizeof(trie[v]));
        index[v]=fail[v]=end[v]=0;
    }

    void init(){
        clear(0);
        n=1;
    }

    int idx(char ch){
        return ch-'a';
    }
    void insert(const char* s,int value=0){
        int v=0;
        for (int x,i=0;s[i];i++){
            x=idx(s[i]);
            if (trie[v][x]==0){
               clear(n);
               trie[v][x]=n++;  
            }
            v=trie[v][x];
        }
        //index[v]=1<<value;
        end[v]++;
    }
    void make(){
        queue<int> q;
        for (int i=0;i<LEAF;i++)
            if (trie[0][i]) q.push(trie[0][i]);
        while (!q.empty()){
            int v=q.front();q.pop();
            //index[v]|=index[fail[v]];
            for (int i=0;i<LEAF;i++){
                int &p=trie[v][i];
                if (p==0) p=trie[fail[v]][i];
                    else{
                    fail[p]=trie[fail[v]][i];
                    q.push(p);
                }
            }
        }
    }
    int find(const char *s){
        int v=0;
        int ans=0;
        for(int i=0; s[i]; i++){
            int x=idx(s[i]);
            v = trie[v][x];
            int y=v;
            while (y){
                  ans += end[y];
                  end[y] = 0; 
                  y = fail[y];   

            }
            //if (end[v]) printf("%d\n",i);
        }
        return ans;
    }
}ac;
}}}

初始化
ac.init()
插入
ac.insert(str)
找fail函数
ac.make()
匹配
ac.find()
index记状态
end记录有几个串结束

#include <iostream>
#include <queue>
using namespace std;
class Automaton{
    public:
    static const int MAXN=500010;
    static const int LEAF=28;
    int trie[MAXN][LEAF],fail[MAXN];
    int end[MAXN];
    int n;
    void clear(int v){
        memset(trie[v],0,sizeof(trie[v]));
        index[v]=fail[v]=end[v]=0;
    }
    void init(){
        clear(0);
        n=1;
    }
    int idx(char ch){
        return ch-'a';
    }
    void insert(const char* s,int value=0){
        int v=0;
        for (int x,i=0;s[i];i++){
            x=idx(s[i]);
            if (trie[v][x]==0){
               clear(n);
               trie[v][x]=n++;  
            }
            v=trie[v][x];
        }
        //index[v]=1<<value;
        end[v]++;
    }
    void make(){
        queue<int> q;
        for (int i=0;i<LEAF;i++)
            if (trie[0][i]) q.push(trie[0][i]);
        while (!q.empty()){
            int v=q.front();q.pop();
            //index[v]|=index[fail[v]];
            for (int i=0;i<LEAF;i++){
                int &p=trie[v][i];
                if (p==0) p=trie[fail[v]][i];
                    else{
                    fail[p]=trie[fail[v]][i];
                    q.push(p);
                }
            }
        }
    }
    int find(const char *s){
        int v=0;
        int ans=0;
        for(int i=0; s[i]; i++){
            int x=idx(s[i]);
            v = trie[v][x];
            int y=v;
            while (y){
                  ans += end[y];
                  end[y] = 0; 
                  y = fail[y];   
            }
            //if (end[v]) printf("%d\n",i);
        }
        return ans;
    }
}ac;