Divljak AC自动机+LCT（含集训队论文集）

听说是2015论文题。。。《浅谈字符串匹配的几种方法》例3 在P41

idea来源：KFDong

对于Alice的串先插到AC自动机里面，然后用Bob的串来贡献答案。

考虑什么时候贡献了答案，一个串P能贡献给Sx答案当且仅当Bob的P串能（沿匹配边或fail边）走到Alice的Sx串终止位置。

所以有一种暴力的做法是，对于新加进来的某个节点，我们暴力沿着这个节点跳fail，如果没更新就更新一下，这样做的复杂度应该可以卡到平方$ n^{4/3}$ 级别。

考虑优化暴力。我上网搜了一下都是一些树链求并的题解，求LCA，dfs序，树状数组，然后T了2333真是喜闻乐见好像论文里就是这种写法。。。

利用树链的并

将所有要处理的节点按照dfs序排序,然后首先把它们到根的路径+1

随后将相邻两个节点的LCA到根的路径-1

非常科学

怎么加?树链剖分?等TLE吧

只需用树状数组维护DFS序即可

可惜卡常数!

用倍增LCA会超时

于是我们换用RMQlca,并用ZKW线段树维护

估计ST表预处理也会超时

然后Orz了kfdong，发现LCT可以直接上！整个人都惊呆了

我的access代码大概长这样：

void access(int t,int las=0){
    for(;t;splay(t),son[t][1]=las,las=t,t=fa[t]);
}

LCT求LCA：假设求lca(x,y)，那么access(x),access(y)，做完y以后的las就是LCA。

对于这道题而言，我们求出fail树，然后在上面维护两个标记，一个是时间戳，另一个是增量。

不是要把树链并起来吗？还是用access，只不过多访问一次时间戳。如果节点t之前的点已经在这一个时间段更新过了，那么就停止access，然后打标记。这样就可以不用容斥了~

然后写一下交一发，发现跑了8s+（我机子慢一个测试点开了O2要跑24s+。。。。真是一个悲伤的故事）

还有什么地方可以优化的呢？

再次Orz了AKF的代码以后，发现他有一个优化，缩点！将不是danger标记的节点统统删掉，这样的话点集规模直接变成了n，然后剩下的该怎么做就怎么做，一下子跑进了4s

试了试IO，好像~~数据有问题还是~~自己写龊了会RE。于是就扔在一边不管了。。。

~~来来来贴代码~~

/**************************************************************
    Problem: 3881
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:3496 ms
    Memory:242856 kb
****************************************************************/

#include<cstdio>
#include<algorithm>
#define N 1620000
int n,m,i,j,fail[N],ch[N][26],tot,las,end[N],q[N],danger[N],id[N];char s[N];
int fa[N],son[N][2],add[N],cnt[N],tim[N],vis[N],tc;
#define ls son[t][0]
#define rs son[t][1]
#define nr(t) (son[fa[t]][0]==t||son[fa[t]][1]==t)
void pd(int t){if(!t)return;
    if(add[t]){
        add[ls]+=add[t],add[rs]+=add[t];
        cnt[ls]+=add[t],cnt[rs]+=add[t];add[t]=0;
    }
    if(tim[ls]<tim[t]||vis[ls]<tim[t])vis[ls]=tim[ls]=tim[t];
    if(tim[rs]<tim[t]||vis[rs]<tim[t])vis[rs]=tim[rs]=tim[t];
}
void rtt(int t){
    int f=fa[t],p=son[f][1]==t;
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1;
    (son[f][p]=son[t][p^1])?fa[son[f][p]]=f:1,son[fa[f]=t][p^1]=f;
}
void pv(int t){if(nr(t))pv(fa[t]);pd(t);}
void splay(int t){int f;
    for(pv(t);nr(t);rtt(t))
    if(f=fa[t],nr(f))rtt(son[f][1]==t^son[fa[f]][1]==f?t:f);
}
void access(int t){int las=0;
    for(;t&&(splay(t),vis[t]<tc);rs=las,las=t,t=fa[t]);
    if(las&&vis[las]<tc)tim[las]=vis[las]=tc,add[las]++,cnt[las]++,splay(las);
}
void build_AC(){
    int l,r,i,j,cnt=1;
    for(q[l=r=0]=0;l<=r;l++)
    for(i=0;i<26;i++)
    if(j=ch[q[l]][i]){
        if(q[l])fail[j]=ch[fail[q[l]]][i];
        q[++r]=j;
    }
    else ch[q[l]][i]=ch[fail[q[l]]][i];
    for(id[0]=i=1;i<=r;i++)
    if(danger[q[i]]){
        id[q[i]]=++cnt;
        fa[cnt]=id[fail[q[i]]];
    }
    else id[q[i]]=id[fail[q[i]]];
}
int main(){
    scanf("%d\n",&n);
    for(i=1;i<=n;i++){
        scanf("%s",s);
        for(las=j=0;s[j];j++){
            s[j]-='a';
            if(!ch[las][s[j]])ch[las][s[j]]=++tot;
            las=ch[las][s[j]];
        }
        end[i]=las;danger[las]=1;
    }
    build_AC();
    for(scanf("%d",&m);m--;){
        scanf("%s",s);
        if(s[0]=='1'){
            scanf("%s",s);tc++;
            for(las=i=0;s[i];i++){
                las=ch[las][s[i]-'a'];
                access(id[las]);
            }
        }
        else{
            scanf("%d",&i);i=id[end[i]];
            pv(i);printf("%d\n",cnt[i]);
        }
    }
}

我并没写过树链剖分但是想想好像不能用在这里？

~~最后打个广告->戳我...别戳前面那个戳我戳我~~

Trinkle的博客

博客

评论

发表评论