posts - 33,  comments - 33,  trackbacks - 0
hdu 2222 多模式串匹配
AC自动机用于多模式串匹配
  1#include <stdio.h>
  2#include <string.h>
  3#include <queue>
  4using namespace std;
  5
  6const int N = 500005;
  7
  8struct Trie
  9{
 10    int flag;
 11    int fail;
 12    int next[26];
 13
 14    void Init()
 15    {
 16        flag = 0;
 17        fail = -1;
 18        for(int i = 0; i < 26; ++i)
 19            next[i] = 0;
 20    }
 21};
 22
 23Trie trieTrees[N];
 24int treeCnt;
 25char strs[1000005];
 26int n;
 27
 28void Insert(char* _str)
 29{
 30    int rt = 0;
 31    while(*_str != 0)
 32    {
 33        int t = *_str - 'a';
 34        if(trieTrees[rt].next[t] == 0)
 35        {
 36            trieTrees[++treeCnt].Init();
 37            trieTrees[rt].next[t] = treeCnt;
 38        }
 39        rt = trieTrees[rt].next[t];
 40        ++_str;
 41    }
 42    trieTrees[rt].flag++;
 43}
 44
 45
 46void BFS()
 47{
 48    queue<int> Queue;
 49    int rt = 0;
 50    int p,q;
 51    Queue.push(0);
 52    while(!Queue.empty())
 53    {
 54        int now = Queue.front();
 55        Queue.pop();
 56        for(int t = 0; t < 26; ++t)
 57        {
 58            if(trieTrees[now].next[t])
 59            {
 60                p = trieTrees[now].fail;
 61                q = trieTrees[now].next[t];
 62                while(p !=-1 && trieTrees[p].next[t] == NULL)
 63                    p = trieTrees[p].fail;
 64                if(p == -1)
 65                    trieTrees[q].fail = 0;
 66                else
 67                    trieTrees[q].fail = trieTrees[p].next[t];
 68                Queue.push(q);
 69            }
 70        }
 71    }
 72}
 73
 74int Match(char *_str)
 75{
 76    int ret = 0;
 77    int rt = 0;
 78    int t,p;
 79    while(*_str)
 80    {
 81        t = *_str - 'a';
 82        if(trieTrees[rt].next[t])
 83            rt = trieTrees[rt].next[t];
 84        else
 85        {
 86            p = trieTrees[rt].fail;
 87            while(p != -1 && (!trieTrees[p].next[t]))
 88                p = trieTrees[p].fail;
 89            if(p == -1)
 90                rt = 0;
 91            else
 92                rt = trieTrees[p].next[t];
 93        }
 94        p = rt;
 95        while(p != 0&& trieTrees[p].flag)
 96        {
 97            if(trieTrees[p].flag)
 98            {
 99                ret += trieTrees[p].flag;
100                trieTrees[p].flag = 0;
101            }
102            p = trieTrees[p].fail;
103        }
104        ++_str;
105    }
106    return ret;
107}
108
109void Test()
110{
111    scanf("%d",&n);
112    treeCnt = 0;
113    trieTrees[0].Init();
114    for(int i = 0; i < n; ++i)
115    {
116        while(gets(strs),strcmp(strs,"") == 0 );
117        Insert(strs);
118    }
119    BFS();
120    gets(strs);
121    int ret = Match(strs);
122    printf("%d\n",ret);
123}
124
125int main()
126{
127    //freopen("data.txt","r",stdin);
128    int testcase;
129    scanf("%d",&testcase);
130    for(int i = 0; i < testcase; ++i)
131        Test();
132    return 0;
133}

posted on 2012-03-29 18:15 bennycen 阅读(1252) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Powered by:
C++博客
Copyright ©2024 bennycen