// trie树，各个字符的长度之和为n。O(n)实现排序
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 26;
const int maxu = 1000000;
const int maxl = 10001;
char pattern[maxl][maxl];
int size = 0;
struct trie
{
trie *child[maxn], *father, *suffix;
char data;
bool isEdge[maxn];
bool isWord;
int ind;
}*root, use[maxu];
void init()
{
memset(use, 0, sizeof(trie) * size);
size = 0;
root = &use[size++];
}
int insert(char* str, int ind)
{
trie* p = root;
while(*str)
{
int i = *str - 'a';
if(p->child[i] == NULL)
{
p->child[i] = &use[size++];
p->child[i]->father = p;
p->child[i]->data = *str;
p->isEdge[i] = true;
p = p->child[i];
}
else
p = p->child[i];
str++;
}
if(p->isWord) // 单词已经存在则返回-1
return -1;
p->isWord = true;
p->ind = ind;
return 0;
}
void DFS(trie* p, int k, char* str, int i)
{
if(p == NULL)
return ;
str[i] = char(k + 'a');
if(p->isWord)
{
str[i+1] = 0;
printf("%s\n", str);
}
for(int j = 0; j < maxn; j++)
{
if (p->isEdge[j])
{
DFS(p->child[j], j, str, i + 1);
}
}
}
void build()
{
int i;
trie* p = root;
p->suffix = root;
queue<trie*> que;
for (i = 0; i < maxn; i++)
{
if (p->child[i])
{
p->child[i]->suffix = root;
que.push(p->child[i]);
}
else
p->child[i] = root;
}
while(!que.empty())
{
p = que.front();
que.pop();
i = p->data - 'a';
// calculate suffix node
if (p->father == root)
{
p->suffix = root;
}
else
{
trie* s = p->father->suffix;
while (s != root)
{
if (s->child[i])
{
p->suffix = s->child[i];
break;
}
s = s->suffix;
}
if (s == root)
{
p->suffix = root->child[i];
}
}
for (i = 0; i < maxn; i++)
{
if (p->child[i])
{
que.push(p->child[i]);
}
else
{
trie* s = p->suffix;
while (s != root)
{
if (s->child[i])
{
p->child[i] = s->child[i];
break;
}
s = s->suffix;
}
if (s == root)
{
p->child[i] = root->child[i];
}
}
}
}
}
int mutimatch(char* str)
{
trie* p = root;
while (p && *str)
{
int ind = *str - 'a';
p = p->child[ind];
if (p->isWord)
{
ind = p->ind;
printf("match %s\n", pattern[ind]);
}
str++;
}
}
int main()
{
int i, j, n;
char str[512];
init();
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%s", &pattern[i]);
insert(pattern[i], i);
}
build();
scanf("%s", str);
mutimatch(str);
for(i = 0; i < maxn; i++)
{
if (root->isEdge[i])
{
DFS(root->child[i], i, str, 0);
}
}
return 0;
}
