[FGISC。Nanro] 未來開端

/*  ACM Q10679 - I Love Strings!! */
/*  559    8100892    2.396    ANSI C    2010-07-15 14:46:26  */
/*  KMP  */ 

#include <stdio.h>
#include <string.h>
#define PSIZE 1005
#define TSIZE 100005

void preproc( char *str, int len, int *z )
{
    /*
        z[i] = t <==> 代表從第i個字元再加上往前 t 個字元和
                      pattern本身的前 t + 1 個字元相等 
        z[i] = -1 <==> 往前沒有符合上面的case，本身也和字串首不同，設為-1 
    */ 
    int i;
    int k = z[0] = -1; /*  初始化，k: 當前字元往前已和前綴success比對的字元數，初始設-1  */    
    for ( i = 1 ; i < len ; i++ )
    {
        /*  從第二個字元(i=1)開始預處理，因將字串首和自己做比對是沒意義的。  */    
        while ( k >= 0 && str[k + 1] != str[i] )  /*  如果前綴的下個字元和當前字元不同  */
            k = z[k];    /*  把k降回當前位置往前success比對的長度，嘗試去往下比，如果不行就繼續砍  */ 
                        /*  會跳兩次的例子：ababac  */ 
        /*  可以往下比了  */ 
        if ( str[k + 1] == str[i] )
            k++;    /*  success比對長度+1  */
        z[i] = k;  /* 記錄當前位置往前最長比對長度 */
    }
}

int KMP( char *T, char *P)
{
    int i, k;
    int z[PSIZE];
    int tlen = strlen(T);
    int plen = strlen(P);
    preproc( P, plen, z );
    k = -1;
    for ( i = 0 ; i < tlen ; i++ )
    {
        while ( k >= 0 && P[k + 1] != T[i] )
            k = z[k];
        if ( P[k + 1] == T[i] )
            k++;
        if ( k + 1 == plen )
        {
            /* 如果還要往下繼續比，就降回當前位置往前最大成功比較字元
               k = z[k] 
             */
            return 1;
        }
    }    
    return 0;
}


int main()
{
    char T[TSIZE], P[PSIZE];
    int N, m;
    scanf("%d", &N);
    while( N-- )
    {
        scanf("%s", T);
        scanf("%d", &m);
        while ( m-- )
        {
            scanf("%s", P);
            if ( KMP(T, P) )
                puts("y");
            else
                puts("n");    
        }
    }
    return 0;
}