NaiveMartin's Blog

namespace acm{
    const int L=2000,M=10;const char W='0';
    int ch[L+10][M+10],fa[L+10],tg[L+10],nw=1;
    void insert(char*s){
        int u=1;for(;*s;++s){
            if(!ch[u][*s-W])ch[u][*s-W]=++nw;
            u=ch[u][*s-W];
        }
        ++tg[u];
    }
    void build(){
        queue<int>qu;
        for(int i=0;i<M;++i)
            if(!ch[1][i])ch[1][i]=1;
            else fa[ch[1][i]]=1,qu.push(ch[1][i]);
        while(!qu.empty()){
            int u=qu.front();qu.pop();
            for(int i=0;i<M;++i)
                if(!ch[u][i])ch[u][i]=ch[fa[u]][i];
                else fa[ch[u][i]]=ch[fa[u]][i],qu.push(ch[u][i]);
        }
    }
}