#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
#define max_size 1500
int root;
int cnt;
struct node
{
int next[26];
int fail;
bool flag;
}st[max_size];
//新建一个节点
void clear()
{
++cnt;
st[cnt].fail = 0;
memset(st[cnt].next, 0, sizeof(st[cnt].next));
}
//插入单词
void insert(char *ch)
{
int p = root;
int i = 0;
while (ch[i])
{
int index = ch[i] - 'a';
if (!st[p].next[index])
{
clear();
st[p].next[index] = cnt;
}
p = st[p].next[index];
}
st[p].flag = true;
}
//生成fail和构建虚节点
void ac_build()
{
queue<int>q;
q.push(root);
int p, x, y, i, k;
while (!q.empty())
{
p = q.front();
q.pop();
for (i = 0; i < 26; i++)
{
if (st[p].next[i])
{
x = st[p].next[i];
y = st[p].fail;
while (y && !st[y].next[i]) y = st[y].fail;
if (!y) st[x].fail = 1;
else st[x].fail = st[y].next[i];
q.push(x);
}
else
{
y = st[p].fail;
while (y && !st[y].next[i]) y = st[y].fail;
if (!y) st[p].next[i] = 1;
else st[p].next[i] = st[y].next[i];
}
}
}
}
int main()
{
return 0;
}