学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2896

这题WA了好多好多次，大概8、9次吧，从cf进行到一半就开始在这调。经过不懈的努力终于发现，TMD，vis的memset放错地方了！！！这都什么事啊，老被这种错给整的那么郁闷。。。

code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std ;
const int kind = 130;
struct node{
    node *fail ;
    node *next[kind] ;
    int count ;
    int id ;
    node(){
       fail = NULL ;
       count = 0 ;
       memset(next, NULL, sizeof(next)) ;
   }
}*q[500001] ;
char keyword[201] ;
char str[10001] ;
int head, tail,ID ;
bool vis[501] ;

void insert(char *str, node *root){
    node *p = root ;
    int i = 0, index ;
    while(str[i]){
        index = str[i] ;
        if(p->next[index]==NULL) p->next[index]=new node() ;
        p = p->next[index] ;
        i ++ ;
    }
    p->count ++ ;
    p->id = ID ++ ;
}
void build_ac_automation(node *root){
    int i ;
    root->fail = NULL ;
    q[head++] = root ;
    while(head!=tail){
        node *temp = q[tail++] ;
        node *p = NULL ;
        for(i=0; i<130; 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] ;
            }
        }
    }
}
int query(node *root){
    int i = 0, cnt = 0, index ;
    node *p = root ;
    while(str[i]){
        index = str[i] ;
        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->count==1){
            cnt += temp->count ;
            vis[temp->id] = true ;
            temp = temp->fail ;
        }
        i ++ ;
    }
    return cnt ;
}
int main(){
    int n, m, sum = 0 ;
    ID = 1 ;
    scanf("%d", &n) ;
    head = tail = 0 ;
    node *root = new node() ;
    for(int i=0; i<n; i++){
        getchar() ;
        scanf("%s", keyword) ;
        insert(keyword, root) ;
    }
    scanf("%d", &m) ;
    build_ac_automation(root) ;
    for(int i=1; i<=m; i++){
        memset(vis, false, sizeof(vis)) ;
        getchar() ;
        scanf("%s", str) ;
        if(query(root)){
            sum ++ ;
            printf("web %d:", i) ;
            for(int j=1; j<=n; j++)
                if(vis[j])  printf(" %d", j) ;
            printf("\n") ;
        }
    }
    printf("total: %d\n", sum) ;
    return 0;}