Aho-corasick

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#define clr( x , y ) memset( x ,y , sizeof x )
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define TAM 100010
#define MOD 1000000007
#define debug( x ) cout << #x << " = " << x << endl
#define f(i,n) for(int i = 0 ; i < n ; i++)
#define ff(i,a,b) for(int i = a ; i < b ; i++)
#define all( x ) x.begin() , x.end()
#define ral( x ) x.rbegin() , x.rend()

using namespace std ;

typedef pair<int,int> ii ;
typedef pair<ii,ii> pii ;
typedef long long ll ;
typedef long double ld ;

struct arist{
    bool final ;
    int next[ 300 ] ;
    int failure ;

    void clean(){
        clr( next , -1 ) ;
        failure = -1 ;
        final = false ;
    }
} ;

arist trie[ TAM ] ;
int pal ;
string alph ;

int nextState( int q , char w ){
    if( q < 0 ) return 0 ;
    if( trie[ q ].next[ w ] != -1 ) return trie[ q ].next[ w ] ;
    if( trie[ q ].failure != -1 ) return nextState( trie[ q ].failure , w ) ;
    return 0 ;
}

void getFailure(){
    queue<int> q ;
    q.push( 0 ) ;
    while( !q.empty() ){
        int nodo = q.front() ; q.pop() ;
        for(char c = 0 ; c < alph.size() ; c++){
            if( trie[ nodo ].next[ c ] != -1 ){
                int p = trie[ nodo ].next[ c ] ;
                trie[ p ].failure = nextState( trie[ nodo ].failure , c ) ;
                if( trie[ trie[ p ].failure ].final )
                    trie[ p ].final = true ;
                q.push( p ) ;
            }
        }
    }
}

char toDict( char c ){
    alph += c ;
    return c ;
}

void build( string S ){
    int n = S.size() ;
    int nodo = 0 ;
    for(int i = 0 ; i < n ; i++){
        char c = toDict( S[ i ] ) ;
        if( trie[ nodo ].next[ c ] == -1 ) trie[ nodo ].next[ c ] = pal++ ;
        nodo = trie[ nodo ].next[ c ] ;
    }
    trie[ nodo ].final = true ;

    getFailure() ;
}

void init(){
    pal = 1 ;
    for(int i = 0 ; i < TAM ; i++) trie[ i ].clean() ;
    alph = "" ;
}

bool match( string S ){
    int n = S.size() ;
    int nodo = 0 ;
    for(int i = 0 ; i < n ; i++){
        char c = S[ i ] ;
        if( trie[ nodo ].next[ c ] == -1 ) return false ;

        nodo = nextState( nodo , c ) ;
    }
    return true ;
//  return trie[ nodo ].final ;
}

int main(){

    int test , q ;
    char S[ TAM ] ;
    scanf("%d" , &test ) ;
    for(int k = 0 ; k < test ; k++){
        init() ;
        scanf("%s" , S ) ;
        build( S ) ;
        scanf("%d" , &q ) ;
        for(int i = 0 ; i < q ; i++){
            scanf("%s" , S ) ;
            int resp = match( S ) ;
            printf("%c\n" , resp ? 'y' : 'n' ) ;
        }
    }
    return 0;
}