「拓扑优化」【AC自动机】拓扑优化

拓扑优化

之前文章中的AC自动机的劣势：要么只能一次跳fail，无法更新所有fail指的点（如图1），要么fail只能一次跳一格（如图二），更新速度最慢可以卡到O（文本串长度*trie树深度）。

优化目的：防止每次到一个点时就更新所有fail的点，大大节省时间
思路：在原来的模板上增加每个点的入度（有几个fail指针指着自己），在最后一次性更新（其实就是用fail指针建边的拓扑），新增内容详见代码
例题：洛谷 p5357

代码：

#include<bits/stdc++.h>
using namespace std;
struct tree{
    int zz[27],fail,val,jl,rd;//rd为入度，jl为记录，记录走过此点的次数，用来统计单词数
}trie[200005];
char st[2000005];
int tot,ans=0,m[200005];//m位标记，m[i]=p 意为单词i的结尾在字典树的p位
void build(int l,int id)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        if(!trie[p].zz[st[i]-'a'])
        {
        	trie[p].zz[st[i]-'a']=++tot;
        }
        p=trie[p].zz[st[i]-'a'];
    }
    trie[p].val=1;
    m[id]=p;//结尾标记
}
void iflose()
{
    int sj,sjs;
    queue<int> q;
    for(int i=0;i<26;i++)
    {
        if(trie[0].zz[i])
        q.push(trie[0].zz[i]);
    }
    while(!q.empty())
    {
        sj=q.front();
        q.pop();
        for(int v,i=0;i<26;i++)
        {
            sjs=trie[sj].zz[i];
            if(sjs==0)
            continue;
            v=trie[sj].fail;
            while(v&&!trie[v].zz[i])v=trie[v].fail;
            if(trie[v].zz[i]!=sjs)
            {
                trie[sjs].fail=trie[v].zz[i];
                trie[trie[v].zz[i]].rd++;         //增加入度
            }
            if(trie[sj].zz[i])
            {
                q.push(trie[sj].zz[i]);
            }
        }
    }
}
void check()
{
    int len=strlen(st),p=0;
    for(int i=0;i<len;i++)
    {
    	while(!trie[p].zz[st[i]-'a']&&p!=0)p=trie[p].fail;
        p=trie[p].zz[st[i]-'a'];
        if(!p)continue;
        trie[p].jl++;
    }
}
queue<int>q;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",st);
        build(strlen(st),i);
    }
    iflose();
    scanf("%s",st);
    check();
    for(int i=1;i<=tot;i++)
    if(trie[i].rd==0)
    q.push(i);               //将所有入度为0的点压进栈
    int sj;
	while(!q.empty())
    {
    	sj=q.front();q.pop();
    	trie[trie[sj].fail].jl+=trie[sj].jl;//给自己的失配指针所指的点x更新
    	trie[trie[sj].fail].rd--;           //删去这条fail边
    	if(trie[trie[sj].fail].rd==0)       //如果删后x入度为0
    	q.push(trie[sj].fail);              //压入栈
    }
    for(int i=1;i<=n;i++)
    printf("%d\n",trie[m[i]].jl);
    return 0;
}

【AC自动机】拓扑优化

拓扑优化

相关阅读

栏目导航

推荐阅读

热门阅读