namespace ACautomaton
{
static const int Sigma=52;
int ch[MAX][30],d[MAX],fail[MAX],tot;
char s[MAX]; int len;
queue<int> q;
inline int getid(char c) {if(c>='a'&&c<='z') return c-'a'; return c-'A'+26;}
void insert(int id)
{
int now=0; len=strlen(s+1);
for(int i=1;i<=len;++i)
{
int to=getid(s[i]);
if(!ch[now][to]) ch[now][to]=++tot;
now=ch[now][to];
}
d[id]=now;
}
inline void build()
{
int now=0;
for(int i=0;i<=Sigma;++i) if(ch[now][i]) q.emplace(ch[now][i]);
while(!q.empty())
{
now=q.front(); q.pop();
G[fail[now]].eb(now);
for(int i=0;i<=Sigma;++i)
if(ch[now][i]) fail[ch[now][i]]=ch[fail[now]][i],q.emplace(ch[now][i]);
else ch[now][i]=ch[fail[now]][i];
}
}
}