#include <cstring>
#include <queue>

#define MAXN 10005
int state[MAXN][26];
bool terminal[MAXN];
int statecount ;
int F[MAXN];

void clear(){
    memset( state ,  0 , sizeof state );// 0 is a not valid state
    memset( terminal , 0 , sizeof terminal );
    statecount = 1;
}

void add(char *s){
    int pos = 0; // and the root too :3
    for( int i = 0 ; s[i] ; ++i ){
        int next = s[i] - 'a';
        if( state[pos][next] == 0 ){
            state[pos][next] = statecount++;
        }
        pos = state[pos][next];
    }
    terminal[pos] = true;
}

void AC(){
    std::queue<int> Q;
    for( int i = 0 ; i < 26 ; ++i ){
        int cur = state[0][i];
        if( cur ){
            F[cur] = 0;
            Q.push(cur);
        }
    }
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for( int i = 0 ; i < 26 ; ++i ){

            int u = state[cur][i];
            if( u ){
                int p = F[cur];
                while( p && state[ p ] [ i ] == 0  )
                    p = F[ p ];
                p = state[p][i];
                F[ u ] = p;
                terminal[ u ] |= terminal[ p ];
                Q.push( u );
            }
        }
    }
}