可以利用主席树在$O(n \log n)$时间内建立AC自动机。

具体方法：

用$\operatorname{map}$建立$\operatorname{trie}$，建立AC自动机时，先把$fail$指针指向的节点的信息继承过来，然后将$\operatorname{map}$中的信息添加进来即可。

AC记录

部分代码

int cot=1,cnt,vis[N],fail[N],rt[N],tr[M],ls[M],rs[M];
map<int,int>t[N];
#define IT map<int,int> :: iterator
// 主席树
void build(int &p,int l,int r)
{
    p=++cnt;
    if (l==r)
    {
        tr[p]=1;
        return;
    }
    int mid(l+r >> 1);
    build(ls[p],l,mid);
    build(rs[p],mid+1,r);
}
void modify(int &u,int v,int l,int r,int x,int y)
{
    u=++cnt;
    ls[u]=ls[v],rs[u]=rs[v];
    if (l==r)
    {
        tr[u]=y;
        return;
    }
    int mid(l+r >> 1);
    if (x<=mid)
        modify(ls[u],ls[v],l,mid,x,y); else
        modify(rs[u],rs[v],mid+1,r,x,y);
}
int calc(int p,int l,int r,int x)
{
    if (!p)
        return 0;
    if (l==r)
        return tr[p];
    int mid(l+r >> 1);
    if (x<=mid)
        return calc(ls[p],l,mid,x); else
        return calc(rs[p],mid+1,r,x);
}
// 插入字符
int ins(int L)
{
    int u(1);
    for (int i=1;i<=L;++i)
    {
        int c(s[i]);
        if (!t[u][c])
            t[u][c]=++cot;
        u=t[u][c];
    }
    ++vis[u];
    return u;
}
// 建立AC自动机
void Build_ACAM()
{
    build(rt[0],0,S);
    fail[1]=0;
    queue<int>q;
    q.push(1);
    while (!q.empty())
    {
        int u(q.front());
        q.pop();
        rt[u]=rt[fail[u]];
        for (IT it=t[u].begin();it!=t[u].end();++it)
        {
            modify(rt[u],rt[u],0,S,it->first,it->second);
            fail[it->second]=calc(rt[fail[u]],0,S,it->first);
            q.push(it->second);
        }
    }
}