HDU 2222(ACオートマトンの2種類のテンプレート)


タイトルリンク


問題はn個の単語をあげて、それからテキスト列をあげます.このテキスト列に現れるn個の単語の数を尋ねる.
iノードの最後の単語数を1つのval[i]で保存すればよい.
2つのテンプレート:
最初のブログ:ブログ
#include
using namespace std;
const int M=60,N=1e6+10;
char s[N];
struct ac_auto
{
    int ne[N][26],val[N],fail[N],sz;
    void init()
    {
        memset(ne[0],0,sizeof(ne[0]));
        sz=0;
    }
    void insert(char *s)// 
    {
        int o=0;
        for(int i=0;s[i];++i)
        {
            int c=s[i]-'a';
            if(ne[o][c]==0){
                ne[o][c]=++sz;
                val[sz]=0;
                memset(ne[sz],0,sizeof(ne[sz]));
            }
            o=ne[o][c];
        }
        val[o]++;
    }
 
    void build()//bfs fail ,   
    {
        queueque;
        for(int i=0;i<26;++i)
        if(ne[0][i]){
            que.push(ne[0][i]);
            fail[ne[0][i]]=0;// fail 
        }
        while(que.size())
        {
            int o=que.front();que.pop();
            for(int i=0;i<26;++i){
                if(ne[o][i])
                {
                    int v=ne[o][i];
                    int fa=fail[o];
                    while(fa&&!ne[fa][i]) fa=fail[fa];//  i  , fail ,  i  
                    fail[v]=ne[fa][i];
                    que.push(v);
                }
            }
        }
    }
 
    int query(char *s)//      fail   
    {
        int o=0,ans=0;
        for(int i=0;s[i];++i)
        {
            int c=s[i]-'a';
            while(!ne[o][c]&&o) o=fail[o];
            o=ne[o][c];
            int tmp=o;
            while(tmp)
            {
                ans+=val[tmp];
                val[tmp]=0;
                tmp=fail[tmp];
            }
        }
        return ans;
    }
}ac;
int main()
{
    int _;cin>>_;while(_--)
    {
        int n;
        scanf("%d",&n);
        ac.init();
        for(int i=1;i<=n;++i){
            scanf("%s",s);
            ac.insert(s);
        }
        ac.build();
        scanf("%s",s);
        printf("%d
",ac.query(s)); } }

 
2つ目のテンプレート:
#include
using namespace std;
const int N=1e6+10;
int n, m;
char s[N];
struct node
{
    int tr[N][26], fail[N], num[N], cnt = 0;
    void init(){
        memset(tr[0], 0, sizeof(tr[0])), cnt=0;
    }

    void insert(char s[]){
        int n = strlen(s + 1), root = 0;
        for(int i = 1; i <= n; ++i){
            if(!tr[root][s[i] - 'a']) {
                tr[root][s[i] - 'a'] = ++cnt;
                memset(tr[cnt], 0, sizeof(tr[cnt])), num[cnt] = 0;
            }
            root = tr[root][s[i]-'a'];
        }
        //printf("cnt:%d root:%d
", cnt, root); num[root]++; } void getfail(){ queue que; for(int i = 0; i < 26; ++i){ if(tr[0][i]) que.push(tr[0][i]), fail[tr[0][i]] = 0; } while(que.size()){ int now = que.front(); que.pop(); for(int i = 0; i < 26; ++i){ if(tr[now][i]) fail[tr[now][i]] = tr[fail[now]][i], que.push(tr[now][i]); else tr[now][i] = tr[fail[now]][i]; } } } int find(char s[]){ int ans = 0; int root = 0, len = strlen(s+1); for(int i = 1; i <= len; ++i){ root = tr[root][s[i] - 'a']; int tmp = root; while(tmp){ //printf("tmp:%d
",tmp); ans += num[tmp]; num[tmp] = 0; tmp = fail[tmp]; } } return ans; } }ac; int main() { int _;scanf("%d", &_);while(_--){ ac.init(); scanf("%d", &n); for(int i = 1; i <= n; ++i){ scanf("%s", s + 1); ac.insert(s); } ac.getfail(); scanf("%s", s+1); printf("%d
", ac.find(s)); } return 0; }

2つのテンプレートの違いはfailポインタを構築するときに異なることです
2つ目は1つ目より少し速いです(個人的には理解しています).failポインタを構築するときにfailを繰り返し踊らないからです.