CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
#include <iostream>
#include 
<queue>
#include 
<cstdio>
#include 
<string>
#include 
<cstring>
using namespace std;

#define max_size 1500
int root;
int cnt;

struct node
{
    
int next[26];
    
int fail;
    
bool flag;
}st[max_size];

//新建一个节点 
void clear()
{
     
++cnt;
     st[cnt].fail 
= 0;
     memset(st[cnt].next, 
0sizeof(st[cnt].next));
}

//插入单词 
void insert(char *ch)
{
     
int p = root;
     
int i = 0;    
     
while (ch[i])
     {
          
int index = ch[i] - 'a';
          
if (!st[p].next[index])
          {
             clear();
             st[p].next[index] 
= cnt;
          }
          p 
= st[p].next[index];
     } 
     st[p].flag 
= true;
}

//生成fail和构建虚节点 
void ac_build()
{
     queue
<int>q;
     q.push(root);
     
int p, x, y, i, k;
     
while (!q.empty())
     {
         p 
= q.front();
         q.pop();
         
for (i = 0; i < 26; i++)
         {
             
if (st[p].next[i])
             {
                 x 
= st[p].next[i];
                 y 
= st[p].fail;
                 
while (y && !st[y].next[i]) y = st[y].fail;
                 
if (!y) st[x].fail = 1;
                 
else st[x].fail = st[y].next[i];
                 q.push(x);
             }
             
else
             {
                 y 
= st[p].fail;
                 
while (y && !st[y].next[i]) y = st[y].fail;
                 
if (!y) st[p].next[i] = 1;
                 
else st[p].next[i] = st[y].next[i];
             }
         }
     }
}

int main()
{
    
return 0;

posted on 2011-05-13 16:04 CodeStream 阅读(311) 评论(0)  编辑 收藏 引用 所属分类: acm_字符串

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