Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

hdu 2222 AC自动机

#include <iostream>
using namespace std;

const int MAXN=50*10005;
const int MAXL=1005;
const int K=26;

struct Node
{
    Node 
*next[K], *fail;
    
int flag, id;
    
void Init(int index)
    
{
        id
=index;
        flag
=0;
        fail
=NULL;
        
for(int i=0; i<K; i++)next[i]=NULL;
    }

}
* Q[MAXN/2], *root, T[MAXN];// Q for queue, root&T for tree;

int index=0;
Node 
* newNode()
{
    T[index].Init(index);
    
return &T[index++];
}


int tokind(char k){return k-'a';}

void insert(char *str)
{    
    
if(root==NULL)
        root
=newNode();

    Node 
*now=root;
    
for(int i=0; str[i]; i++)
    
{
        
int kind=tokind(str[i]);
        
if(now->next[kind]==NULL)
            now
->next[kind]=newNode();
        now
=now->next[kind];
    }

    now
->flag++;
}


void buildAC()
{
    
int head=0, tail=0;
    root
->fail=NULL;

    Q[tail
++]=root;
    
while(head<tail)
    
{
        Node 
*now=Q[head++];
        
for(int i=0; i<K; i++)
        
{
            
if(now->next[i]!=NULL)
            
{
                
if(now==root)now->next[i]->fail=root;
                
else
                
{
                    Node 
*p=now->fail;
                    
while(p->next[i]==NULL&&p!=root)p=p->fail;
                    p
=p->next[i];
                    now
->next[i]->fail=(p==NULL)?root:p;
                }

                Q[tail
++]=now->next[i];
            }

        }

    }

}


int query(char *str)
{
    
int res=0;
    Node 
*p=root;
    
for(int i=0; str[i]; i++)
    
{
        
int kind=tokind(str[i]);
        
while(p->next[kind]==NULL&&p!=root)p=p->fail;
        p
=p->next[kind];
        p
=(p==NULL)?root:p;
        Node 
*now=p;
        
while(now!=root&&now->flag!=-1)
        
{
            res
+=now->flag;
            now
->flag=-1;
            now
=now->fail;
        }

    }

    
return res;
}


int main()
{
    
//freopen ("in.txt", "r", stdin);
    int T;
    scanf(
"%d"&T);
    
while(T--)
    
{
        
int n;
        root
=NULL;
        scanf(
"%d",&n);getchar();        
        
while(n--)
        
{
            
char str[55];
            scanf(
"%s",str);
            insert(str);
        }

        buildAC();
        
char ch[1000005];
        scanf(
"%s",ch);
        printf(
"%d\n",query(ch));
    }

    
return 0;
}

posted on 2012-04-13 15:17 Drolca 阅读(136) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理