**ac_automation: multipattern match algorithm
*input: n patterns and string
*output: all the patterns that appear in the string
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 26
struct node {
    struct node *fail;
    struct node *next[N];
    int count;
    
};

typedef struct node Node;

void init_node(Node *p) //initialize the tree node
{
    int i;

    p->fail = NULL;
    for (i = 0; i < N; ++i)
        p->next[i] = NULL;
    p->count = 0;
}

int h(char str[]) //translate string into state
{
    if (strcmp(str, "she") == 0)
        return 1;
    if (strcmp(str, "he") == 0)
        return 2;
    if (strcmp(str, "say") == 0)
        return 3;
    if (strcmp(str, "shr") == 0)
        return 4;
    if (strcmp(str, "her") == 0)
        return 5;
}

void f(int s) //translate state into string
{
    switch (s) {
    case 1:
        puts("she");
        break;
    case 2:
        puts("he");
        break;
    case 3:
        puts("say");
        break;
    case 4:
        puts("shr");
        break;
    case 5:
        puts("her");
    }
}

void insert(char str[], Node *root) //insert str into prefix tree
{
    int i, idx;
    Node *p = root;

    i = 0;
    while (str[i]) {
        idx = str[i] - 'a';
        if (p->next[idx] == NULL) { //there is no node i in prefix tree, so create it
            p->next[idx] = (Node *)malloc(sizeof(Node));
            init_node(p->next[idx]); //remember initilize it 
        }
        p = p->next[idx];
        ++i;
    }
    p->count = h(str); //str to number(accepted state)
}

/*
 *travel the prefix tree and print all the pattern
 */
void travel(char str[], int ord, Node *p) 
{
    if (p->count) {//found a pattern and print it
        str[ord] = '\0';
        printf("%s\n", str);
    }
    int i;
    for (i = 0; i < N; ++i) {
        if (p->next[i]) {
            str[ord++] = 'a' + i;
            travel(str, ord, p->next[i]);
            ord--;//ord goes back
        }
    }
}

/*
 *free all the nodes in prefix tree
 *(it is a postorder travel)
 */
void free_tree(Node *root)
{
    Node *p = root;
    int i;
    //free all the child trees of p
    for (i = 0; i < N; ++i) {
        if (p->next[i])
            free_tree(p->next[i]);
    }
    free(p);
}

#define SIZEQ 100000
Node *q[SIZEQ]; //the queue that stores the tree node

void build_ac_machine(Node *root)
{
    root->fail = NULL;
    int head = 0, tail = 0;
    int i;
    Node *p, *cur;
    q[tail++] = root;
    while (head != tail) {//while the queue is not empty
        p = NULL;
        cur = q[head++];
        for (i = 0; i < N; ++i) {
            if (cur->next[i] != NULL) { //current node has a child i
                if (cur == root) //the fail pointer of the root point to the root
                    cur->next[i]->fail = root;
                else {
                    p = cur->fail; //p point to the fail pointer of current node
                    while (p != NULL) {
                        if (p->next[i] != NULL) { //p has a child i, so
                            cur->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL)
                        cur->next[i]->fail = root;
                }
                q[tail++] = cur->next[i]; //make child i into the queue
                //printf("%c\n", i + 'a');
            }
        }
    }
}

/*
 * query and print all the patterns that contained
 * in str
 */
int query(char str[], Node *root)
{
    int i, idx, cnt = 0;
    Node *p = root, *tmp;

    i = 0;
    while (str[i]) {
        idx = str[i] - 'a';
        //check if str[0..i] can match with some patterns
        while (p->next[idx] == NULL && p != root)
            p = p->fail;
        p = p->next[idx];
        if (p == NULL)
            p = root;
        tmp = p;
        while (tmp != root) {
            //cnt += tmp->count;
            //tmp->count = 0;
            if (tmp->count) { //found pattern
                printf("\nfound pattern: ");
                f(tmp->count);
                ++cnt;
            }
            tmp = tmp->fail;
        }
        ++i;
    }
    return cnt;
}

#define SIZESTR 10000
#define SIZEPAT 50

int main(void)
{
    Node *root = (Node *)malloc(sizeof(Node));
    init_node(root);
    char str[SIZESTR], pat[SIZEPAT];
    int n;

    scanf("%d", &n);
    while (n--) { //insert n patterns into prefix tree
        scanf("%s", pat);
        insert(pat, root);
    }
    //puts("");
    //travel(str, 0, root);
    build_ac_machine(root);
    while (scanf("%s", str) != EOF) {
        int cnt = query(str, root);
        if (cnt == 0)
            printf("\nere is no pattern appears in string\n");
    }
    free_tree(root);
    return 0;
}