untested aho-corasick

char str[MAX];char s[2005];int n,len,exist[1005];

struct trie{

  trie *next[130];
  trie *suff;
  vector<int>vec;
  trie(){
    for(int i = 0;i<130;i++){

        next[i] = NULL;
    }
    vec.clear();
    suff = NULL;
  }
}*root;

void Insert(string t,int pos){
    trie *curr = root;
    for(int i = 0;i<t.length();i++){

        int id = t[i] - 32;
        if(curr->next[id]==NULL){

            curr->next[id] = new trie();
        }
        curr = curr->next[id];

    }
    curr->vec.pb(pos);
}

void propagate(trie *curr){

    if(curr==root)return ;
    for(int i = 0;i<(int)curr->suff->vec.size();i++){

        curr->vec.pb(curr->suff->vec[i]);
    }

}

void failure(){
    queue<trie *>q;
    q.push(root);
    while(!q.empty()){
        trie *curr = q.front();
        q.pop();
        for(int c = 0;c<100;c++){
            int id = c;
            if(curr->next[id]){

                if(curr==root){

                    curr->next[id]->suff = root;
                }
                else {
                    trie *tmp = curr;
                    while(tmp->suff!=NULL){

                        if(tmp->suff->next[id]){

                            curr->next[id]->suff = tmp->suff->next[id];
                            break;
                        }
                        tmp = tmp->suff;
                    }
                    if(tmp->suff==NULL)curr->next[id]->suff = root;

                }
                propagate(curr->next[id]);
                q.push(curr->next[id]);

            }
        }
    }
}

void Search(){
    int indx = 0;
    trie *curr = root;
    while(indx<len){

        int id = str[indx] -32;
        while(curr!=root&&curr->next[id]==NULL)curr = curr->suff;
        if(curr->next[id]){
            curr = curr->next[id];
            trie *tmp = curr;

            if(tmp!=root&&(int)tmp->vec.size()){

                for(int i = 0;i<(int)tmp->vec.size();i++){

                    exist[tmp->vec[i]] ++;
                }
            }

        }
        indx++;
    }

}


int main()
{
    booster()
    ///read("input.txt");

    while(scanf("%s",str)!=EOF)
    {
        root = new trie();
        mem(exist,0);
        len = strlen(str);
        scani(n);
        for(int i = 0;i<n;i++){

            scanf(" %s",s);
            Insert(s,i);
        }
//        printf("%s\n",str);
//        for(int i = 0;i<n;i++)printf("%s\n",s[i]);
        failure();

        Search();
        for(int i = 0;i<n;i++){
            if(exist[i])printf("Y\n");
            else printf("N\n");

        }
    }


    return 0;
}