程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2222 Keyword Search AC自動機模板

HDU 2222 Keyword Search AC自動機模板

編輯：C++入門知識

HDU 2222 Keyword Search AC自動機模板

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 20071027

using namespace std;

const int MAXN = 26;

struct N
{
    int next[MAXN],fail,flag;
}st[500010];

bool vis[500010];

int Top;

int creat()
{
    memset(st[Top].next,-1,sizeof(st[Top].next));
    st[Top].fail = -1,st[Top].flag = 0;
    return Top++;
}

char s[1000010];

inline int sel(char tar)
{
    return (tar-'a');
}

int Get_Fail(int site,int tar)
{
    while(1)
    {
        if(site == -1)
            return 0;
        if(st[site].next[tar] != -1)
            return st[site].next[tar];
        site = st[site].fail;
    }
}

queue q;

void Get_Fail(int root)
{
    st[root].fail = -1;

    q.push(root);

    int f;

    while(q.empty() == false)
    {
        f = q.front();
        q.pop();

        for(int i = 0; i < MAXN; ++i)
        {
            if(st[f].next[i] != -1)
            {
                st[st[f].next[i]].fail = Get_Fail(st[f].fail,i);
                q.push(st[f].next[i]);
            }
        }
    }
}

//pre記錄當前的節點的父節點，為了尋找fail指針
void Get_Trie(int root,char *s,int site)
{
    while(s[site] != '\0')
    {
        if(st[root].next[sel(s[site])] == -1)
            st[root].next[sel(s[site])] = creat();
        root = st[root].next[sel(s[site])];
        ++site;
    }
    
    st[root].flag++;
}

int Match(int root,char *s,int site)
{
    int ans = 0,p = root,tmp;

    for(site = 1; s[site] != '\0' ; ++site)
    {
        while(p != -1 && st[p].next[sel(s[site])] == -1)
            p = st[p].fail;

        if(p == -1)
        {
            p = root;
            continue;
        }
        p = st[p].next[sel(s[site])];

        tmp = p;

        while(tmp != root && st[tmp].flag != -1)
        {
            if(st[tmp].flag)
            {
                ans += st[tmp].flag;
                st[tmp].flag = -1;
            }
            tmp = st[tmp].fail;
        }
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);

    int n,root,i;

    while(T--)
    {
        Top = 0;
        root = creat();

        scanf("%d",&n);

        for(i = 1; i <= n; ++i)
        {
            scanf("%s",s+1);
            Get_Trie(root,s,1);
        }

        Get_Fail(root);

        scanf("%s",s+1);

        printf("%d\n",Match(root,s,1));
    }

    return 0;
}