hdu 3065

AC自动机。。建好字典树，找到fail指针。然后查询。存模版题，需要注意当查到不是大写字母的时候要 改变p=root.而且字符串可以重复出现。

[cpp] 
#include<cstdio> 
#include<cstring> 
using namespace std; 
char str[2000100]; 
int head,tail; 
struct node{ 
    node *fail; 
    node *next[26]; 
    int cnt,id; 
    node(){ 
       cnt=0;  fail=NULL; memset(next,NULL,sizeof(next)); 
    } www.2cto.com
} *q[500000]; 
char s[1010][55]; 
int cnt[1010]; 
void insert(node *root,char str[],int id){ 
    node *p=root;  int i=0; 
    while(str[i]){ 
        int index=str[i]-'A'; 
        if(p->next[index]==NULL)  p->next[index]=new node(); 
        p=p->next[index];  i++; 
    } 
    p->cnt++;   p->id=id; 
} 
void build_ac(node *root){ 
    node *p=NULL; 
    q[head++]=root; 
    while(head!=tail){ 
        node *temp = q[tail++]; 
        for(int i=0;i<26;i++){ 
            if(temp->next[i]!=NULL){ 
                if(temp==root)  temp->next[i]->fail=root; 
               else{ 
                   p=temp->fail; 
                   while(p!=NULL){ 
                       if(p->next[i]!=NULL){ 
                            temp->next[i]->fail=p->next[i]; 
                            break; 
                       } 
                       p=p->fail; 
                   } 
                   if(p==NULL)  temp->next[i]->fail=root; 
               } 
               q[head++]=temp->next[i]; 
            } 
        } 
    } 
} 
void query(node *root){ 
    int i=0;  node *p=root;  int index; 
    while(str[i]){ 
       if(str[i]>='A'&&str[i]<='Z'){ 
           index=str[i]-'A'; 
           while(p->next[index]==NULL&&p!=root)  p=p->fail; 
           p=p->next[index]; 
           p=(p==NULL)?root:p; 
           node *temp=p; 
           while(temp!=root&&temp->cnt>0){ 
                cnt[ temp->id ]++; 
                temp=temp->fail; 
           } 
       } 
       else 
          p=root; 
       i++; 
    } 
} 
 
int main(){ 
    int n; 
    while(scanf("%d",&n)!=EOF){ 
        memset(cnt,0,sizeof(cnt)); 
        node *root=new node(); 
        head=tail=0; 
        for(int i=0;i<n;i++)  scanf("%s",&s[i]),insert(root,s[i],i+1); 
        build_ac(root); 
        scanf("%s",str); 
        query(root); 
 
        for(int i=1;i<=n;i++){ 
            if(cnt[i]>0){ 
               printf("%s: %d/n",s[i-1],cnt[i]); 
            } 
        } 
    } 
    return 0; 
 
}