hdu 2896 病毒侵袭 ac自动机

/*
hdu 2896 病毒侵袭 ac自动机
从题意得知，模式串中没有重复的串出现，所以结构体中可以将last[]（后缀链接）数组去掉
last[]数组主要是记录具有相同后缀模式串的末尾节点编号 。本题中主要是计算每一个模式串
在主串中有没有出现过，而不是计算出现过多少次，所以将last[]数组省掉....
*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 210*500
using namespace std;
class AC_atomata
{
public:
   int trie[N][128],  f[N], val[N];
   int vis[510];
   int nodeN;
   int total;
   queue<int>q;
   void init()
   {
      nodeN=0;
      val[0]=0;
      total=0;
      while(!q.empty()) q.pop();
      memset(trie[0], 0, sizeof(trie[0]));
   }
   void build(char *str, int index);//建立trie树
   void getFail();//失配函数
   void find(char *T, int n, int index);//查找函数
};

void AC_atomata::build(char *str, int index)
{
    int i, u;
    for(i=0, u=0; str[i]; ++i)
    {
        int ch=str[i];
        if(!trie[u][ch])
        {
            trie[u][ch]=++nodeN;
            memset(trie[nodeN], 0, sizeof(trie[nodeN]));
    }
    u=trie[u][ch];
    val[u]=0;
    }
    val[u]=index;
}

void AC_atomata::getFail()
{
   int r, u, v, i;
   f[0]=0;
   for(i=0; i<128; ++i)
   {
       if(trie[0][i])
       {
             q.push(trie[0][i]);
             f[trie[0][i]]=0;
       }
   }
   while(!q.empty())
   {
      r=q.front();
      q.pop();
      for(i=0; i<128; ++i)
      {
            u=trie[r][i];
            if(!u) continue;
            q.push(u);
            v=f[r];
            while(v && !trie[v][i]) v=trie[v][i];
            f[u]=trie[v][i];
      }
   }
}

void AC_atomata::find(char *T, int n, int index)
{
    int i, u;
    int cnt=0, v[3];
    memset(v, 0, sizeof(v));
    memset(vis, 0, sizeof(vis));//每一次查找将数组初始化，开始忘记初始化了， 哇了好多次
    for(i=0, u=0; T[i]; ++i)
    {
        int ch=T[i];
        while(u && !trie[u][ch])  u=f[u];
        u=trie[u][ch];
        if(val[u] && !vis[val[u]])
        {
            v[cnt++]=val[u];
            vis[val[u]]=1;
            if(cnt>2) break;
        }
    }
    if(cnt>0)
    {
        ++total;
        printf("web %d:", index);
        sort(v, v+3);
        for(i=0; i<3; ++i)
           if(v[i])  printf(" %d", v[i]);
        printf("\n");
    }
}

AC_atomata ac;
char T[10005], s[205];

int main()
{
   int n, m, i;
   while(scanf("%d", &n)!=EOF)
   {
       ac.init();
       for(i=1; i<=n; ++i)
        {
           scanf("%s", s);
           ac.build(s, i);
    }
       ac.getFail();
       scanf("%d", &m);
       for(i=1; i<=m; ++i)
       {
             scanf("%s", T);
             ac.find(T, n, i);
       }
       printf("total: %d\n", ac.total);
   }
   return 0;
}
/*
    上面的程序过了，感觉数据很水....
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 100005
#define M 505
using namespace std;
int n, m;
class AC_atomata
{
public:
    int trie[N][128], fail[N];
    int cnt;
    int vis[M];//标记边
    int nodeN;//节点数
    int val[N];//标记字符节点是否为单词末尾
    queue<int>q;
    void init();
    void build(char *T, int index) ;
    void getFail();
    void find(char *S, int index);
};

void AC_atomata:: init()
{
   while(!q.empty())  q.pop();
   memset(trie[0], 0, sizeof(trie[0]));
   nodeN=0;
   cnt=0;
   memset(val, 0, sizeof(val));
}

void AC_atomata:: build(char *T, int index)
{
    int i, u=0;
    for(i=0; T[i]; ++i)
    {
        if(trie[u][T[i]]==0)
        {
            trie[u][T[i]]=++nodeN;
            memset(trie[nodeN], 0, sizeof(trie[nodeN]));
    }
    val[u]=0;
    u=trie[u][T[i]];
    }
    val[u]=index;
}

void AC_atomata:: getFail()
{
    int r, u, v;
    int c, root=0;
    fail[root]=0;
    for(c=0; c<128; ++c)
    {
        if(v=trie[root][c])
        {
            fail[v]=root;
            q.push(v);
    }
    }
    while(!q.empty())
    {
        r=q.front(); q.pop();
    for(c=0; c<128; ++c)
    {
        u=trie[r][c];
        if(!u)//该节点不存在，也就是查找过程中每一个节点都是平等的
           trie[r][c]=trie[fail[r]][c];
        else
        {
            fail[u]=trie[fail[r]][c];
            q.push(u);
        }
    }
    }
} 

void AC_atomata:: find(char *S, int index)
{
   int cur, root, count=0;
   cur=root=0;
   memset(vis, 0, sizeof(vis));
   for(int i=0; S[i]; ++i)
   {
       cur=trie[cur][S[i]];
       int next=cur;

          //这个while循环就是last[]数组实现的功能，只不过是last[]数组记录的总是单词结尾字符的节点的编号
          //而我们通过沿着 next 节点的失配方向一直搜索， 也可以寻找到 以next节点所对应字符结尾的单词
       while(next!=root)
       {
              if(val[next])
                 {
              vis[val[next]]=1;
              count++;
          }
              next=fail[next];
       }
   }
   if(count>0)
   {
       ++cnt;
       printf("web %d:", index);
       for(int i=1; i<=n; ++i)
         if(vis[i])
           printf(" %d", i);
       printf("\n");
   }
} 

char t[205], s[10005];
AC_atomata ac;
int main()
{
   int i;
   while(scanf("%d", &n)!=EOF)
   {
       ac.init();
       for(i=1; i<=n; ++i)
       {
             scanf("%s", t);
             ac.build(t, i);
       }
       ac.getFail();
       scanf("%d", &m) ;
       for(i=1; i<=m; ++i)
       {
             scanf("%s", s);
             ac.find(s, i);
       }
       printf("total: %d\n", ac.cnt);
   }
   return 0;
}