Hmmmmmm…………strings again :) Then it must be aneasy task for you. Well……you are given with a string S of length notmore than 100,000 characters (only ‘a’-‘z’ and ‘A’ – ‘Z’). Then follows q (q< 1000) queries where each query contains a string T of maximumlength 1,000 (also contains only ‘a’-‘z’ and ‘A’ – ‘Z’). You should determinewhether or not T is a substring of S.

Input
       First line contains an integer k (k< 10) telling the number of test cases to follow. Each test case beginswith S. It is followed by q. After this line there are qlines each of which has a string T as defined before.

Output
       For each query print ‘y’ if it is a substringof S or ‘n’ otherwise followed by a new line. See the sample outputbelow.

Sample Input
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz

Sample Output
y
n
y

---

怕會有重複的 T, 因此多用了一個 map
第一次實做 AC自動機, 請多見諒

//C++ 180ms

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define maxKind 52
using namespace std;

struct Node{
    Node *fail;
    Node *next[maxKind];
    int cnt;
    int who;
    Node() {
        fail = NULL;
        cnt = 0;
        who = 0;
        memset(next, 0, sizeof(next));
    }
};

void build_Trie(const char* str, Node *root, int who) {
    Node *p = root;
    int i = 0, idx;
    while(str[i]) {
        if(str[i] >= 'A' && str[i] <= 'Z')
            idx = str[i]-'A';
        else
            idx = str[i]-'a'+26;
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
        }
        p = p->next[idx];
        i++;
    }
    p->cnt++;
    p->who = who;
}
void build_AC_automation(Node *root) {
    root->fail = NULL;
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] == NULL)
                continue;
            Q.push(tn->next[i]);
            p = tn->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                tn->next[i]->fail = root;
            else
                tn->next[i]->fail = p->next[i];
        }
    }
}
void free_AC_automation(Node *root) {
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] != NULL) {
                Q.push(tn->next[i]);
            }
        }
        free(tn);
    }
}
void query(const char* str, Node *root, int cnt[]) {
    int i = 0, idx;
    Node *tn, *p;
    tn = root;
    while(str[i]) {
        if(str[i] >= 'A' && str[i] <= 'Z')
            idx = str[i]-'A';
        else
            idx = str[i]-'a'+26;
        while(tn->next[idx] == NULL && tn != root)
            tn = tn->fail;
        tn = tn->next[idx];
        tn = (tn == NULL) ? root : tn;
        p = tn;
        while(p != root && p->cnt != -1) {
            /*
                cnt += p->cnt;
                p->cnt = 0;
            */
            cnt[p->who] = 1;
            p->cnt = -1;
            p = p->fail;
        }
        i++;
    }
}
char buf[100001];
int main() {
    int t, n;
    scanf("%d", &t);
    getchar();
    map<string, int> record;
    string S, T[1001];
    while(t--) {
        gets(buf);
        S = buf;
        scanf("%d", &n);
        record.clear();
        getchar();
        Node *root = new Node();
        int encode = 0;
        for(int i = 0; i < n; i++) {
            gets(buf);
            T[i] = buf;
            if(record[T[i]] == 0)
                record[T[i]] = ++encode;
            build_Trie(T[i].c_str(), root, record[T[i]]);
        }
        int cnt[1001] = {};
        build_AC_automation(root);
        query(S.c_str(), root, cnt);
        free_AC_automation(root);
        for(int i = 0; i < n; i++) {
            int num = record[T[i]];
            printf("%c\n", cnt[num] == 0 ? 'n' : 'y');
        }
    }
    return 0;
}