首页 > 其他分享 >AC自动机

AC自动机

时间:2024-02-17 15:33:53浏览次数:25  
标签:AC int Fail son trie fail 自动机

AC 自动机

·赘述与前置


让大家失望の是, \(AC\) 自动机不是让你自动 \(\color{green}Accepted\) 的机器。

其实可以将 \(AC\) 自动机理解成一个在 \(Trie\) 树上跑的 \(KMP\)

此处的 \(KMP\)指的是一种算法思想,即利用失配时的有限信息来缩小时间复杂度,并不是真正的 \(KMP\).

\(\bf{前置知识:}\)

\(Tire\)树,以及 \(KMP\) 算法思想


· \(First\) --用途与 \(Fail\) 指针


·用途

当给你一个模式串和一个目标串求解模式串的出现次数时,你会选择 \(KMP\) ;

但如果给你一堆模式串和一个目标串让你求解其总出现次数时, \(KMP\) 会 \(T\) .

这时,\(AC自动机,启动!\)

此为\(AC\)自动机求解的东西。


· \(Fail\) 指针

首要任务,是将这些模式串一股脑的塞进一棵 \(Trie\) 树里。

但在树里单个匹配,还是很慢。

此时仿照 \(KMP\) 的思想 , 使用失配指针 ( \(Fail\) )。


· \(Fail\) 含义

若 \(i\) の失配指针指到 \(j\) , 则从树根到 \(j\) 的这一段是从树根到 \(i\) 这一段的 \(最长后缀\)

为什么要存这个呢?

当我们匹配完 \(i\) 后, \(i\) 前面的任何一个连续的段都在这一目标串内被匹配。

如果存后缀的话,那么正好能接上 \(j\) 的儿子节点。

最长的话,那可以考虑,后面的还会接上此处,使之变短。

当然 \(fail\) 的作用是使 \(Tire\) 树变为有向图 ,方便以后的操作。


· \(Fail\) 的特性

  1. \(root\) 的 \(fail\) 指向他自己。

  2. \(root\) 的儿子的 \(fail\) 指针是 \(root\)

  3. \(i\) 的 \(fail_i\) 的深度一定小于 \(i\) (显然的)


· \(Fail\) の求法

使用函数 \(Get\) _ \(Fail\)

首先我们将 \(0\) 的所有儿子全部指向 \(1\) 。(我们定义 $ 1 $ 是根 )

再将 \(1\) 放入队列之中 。

暴力枚举队首元素的各个儿子节点(此编号没儿子也枚举)。

  1. 如果他没有这个编号的儿子,那么他的这个编号的儿子是他的 \(fail\) 指针指向的点的这个编号的儿子。如果也没有,没关系,会指向根 ( $ 1 $ ) ;

  2. 如果他有这么一个儿子,那么这个儿子的 \(fail\) 指针指向:他父亲的的 \(fail\) 指针指向的点的这个编号的儿子

建议消化吸收一下。

自己手画几个图,就能明白什么意思了。

· \(Code\)

void Get_Fail( )
{
    queue < int > q ; 
    for( int i = 0 ; i < 26 ; ++ i )
    {
        trie[ 0 ].son[ i ] = 1 ; 
    }
    q.push( 1 ) ; 
    while ( !q.empty( ) )
    {
        int k = q.front( ) , failed = trie[ k ].fail ; q.pop( ) ; 
        for( int i = 0 ; i < 26 ; ++ i ) //暴力枚举队首元素的各个儿子节点。
        {
            int y = trie[ k ].son[ i ] ; 
            if( !y ) //1.
            {
                trie[ k ].son[ i ] = trie[ failed ].son[ i ] ; 
                continue ; 
            }
            trie[ y ].fail = trie[ failed ].son[ i ] ; // 2. 
            q.push( y ) ; 
        } 
    }
}

· \(Second\) -- 查询操作

既然已知 \(Fail\) 了,那如何查询呢?(-_-)3 (挠头)

我们可以将目标串直接扔进 \(AC\) 自动机中匹配去

将经历过的点的 \(back\) 值标成 \(-1\),意为不可再进。

然后就暴力跳 $ fail $ ,具体看代码。

· \(Code\)

int query( char s[ ] )
{
	int u = 1 , ans = 0 , len = strlen( s ) ; 
	for(int i = 0 ; i < len ; i ++ ) 
    {
		int v = s[ i ] - 'a' ;
		int k = trie[ u ].son[ v ] ;		//跳Fail
		while( k > 1 && trie[ k ].back != - 1 ) //经过就不统计了
        { 	
			ans += trie[ k ].back , trie[ k ].back = - 1 ; 	//累加上这个位置模式串个数,标记已经过
			k = trie[ k ].fail ; 			//继续跳Fail
		}
		u = trie[ u ].son[ v ] ; 
	}
	return ans ; 
}

· \(Third\) -- 优化 - > 拓扑排序


·如何优

上述代码的时间复杂度是有点小高的, \(Query\) 中暴力跳 \(Fail\) 的复杂度是 \(O( \ 模式串长度 \times 目标串长度 \ )\)

考虑优化。

我们发现其实大多数时间消耗在了跳 \(Fail\) 那里。

那如果我们从每一条由 \(Fail\) 指针连成的链,链头开始往下跳,能优化。

那么如何改变目标串的插入模式而得到优化呢?

我们可以还是让他在 \(AC\) 自动机上跑,在他每个经过的点增加标记,这样:

以他开始的,即他后面的(跳 \(Fail\) ) \(+=\) 这里的标记,因为比后面的长的都能匹配,那他也能匹配。而这个位置以前的标记数是跳到他自己的或其他的跑到他的,与新加的无关。

那么代码就清晰了。


· $Code \ of \ GetFail $

就在 \(y\) 定义出 \(Fail\) 时后增加 $ y の Fail $ 的入度:

in[ trie[ y ].fail ] ++ ; 

· $Code \ of \ Query $

精简很多了。

inline void query( char Checkee[ ] , int length )
{
    int x = 1 ; 
    for ( int i = 1 ; i <= length ; ++ i )
    {
        int j = Checkee[ i ] - 'a' ; 
        x = trie[ x ].son[ j ] ; 
        trie[ x ].ans ++ ; 
    }
}

· $Code \ of \ Topu $

严格按照上面的走

inline void Topu( )
{
    queue < int > q ; 
    for ( int i = 1 ; i <= numbol ; ++ i )
    {
        if( !in[ i ] )q.push( i ) ; 
    }
    while ( !q.empty( ) ) 
    {
        int k = q.front( ) ; q.pop( ) ; 
        vis[ trie[ k ].back ] = trie[ k ].ans ; 
        int y = trie[ k ].fail ; in[ y ] -- ; 
        trie[ y ].ans += trie[ k ].ans ; 
        if( !in[ y ] ) q.push( y ) ; 
    }
}

· 整体の代码

$ Keywords \ Search \ (HZOI) $

$ Keywords \ Search \ (vjudge) $

$ Keywords \ Search \ (Loj) $

给定 $ n $ 个长度不超过 $ 50 $ 的由小写英文字母组成的单词准备查询,以及一篇长为 $ m $ 的文章,问:文中出现了多少个待查询的单词。多组数据。

对于全部数据,$ 1≤n≤10^4 $ , $ 1≤m≤10^6 $ 。

$ code : (Topu) $



#include<bits/stdc++.h>
const int N = 2e4 + 100 ; 
const int M = 1e6 + 10 ; 
using namespace std ; 
char s[ N ] , Che[ M ] ; 
int in[ N ] , vis[ N ] ; 
int t , Map[ N ] ;  
bool use[ N ] ; 
struct Tire_AC_
{
    int numbol = 1 ;  
    struct One_Node
    {
        int son[ 27 ] , fail , back , ans ; 
    }trie[ N ] ; 
    inline void insert( char Checkee[ ] , int length , int id )
    {
        int x = 1 ; 
        for ( int i = 1 ; i <= length ; ++ i )
        {
            int j = Checkee[ i ] - 'a' ; 
            if ( !trie[ x ].son[ j ] )
            {
                trie[ x ].son[ j ] = ++ numbol ; 
            }
            x = trie[ x ].son[ j ] ; 
        }
        if( !trie[ x ].back ) trie[ x ].back = id ; 
        Map[ id ] = trie[ x ].back ; 
    }
    inline void Get_fail( )
    {
        queue < int > q ; 
        for ( int i = 0 ; i < 26 ; ++ i )
        {
            trie[ 0 ].son[ i ] = 1 ; 
        }
        q.push( 1 ) ; 
        while ( !q.empty( ) )
        {
            int k = q.front( ) ; q.pop( ) ; 
            for( int i = 0 ; i < 26 ; ++ i )
            {
                int y = trie[ k ].son[ i ] , failed = trie[ k ].fail ; 
                if( !y )
                {
                    trie[ k ].son[ i ] = trie[ failed ].son[ i ] ; 
                    continue ; 
                }
                trie[ y ].fail = trie[ failed ].son[ i ] ; in[ trie[ y ].fail ] ++ ; 
                q.push( y ) ;  
            } 
        }
    }
    inline void query( char Checkee[ ] , int length )
    {
        int x = 1 ; 
        for ( int i = 1 ; i <= length ; ++ i )
        {
            int j = Checkee[ i ] - 'a' ; 
            x = trie[ x ].son[ j ] ; 
            trie[ x ].ans ++ ; 
        }
    }
    inline void Topu( )
    {
        queue < int > q ; 
        for ( int i = 1 ; i <= numbol ; ++ i )
        {
            if( !in[ i ] )q.push( i ) ; 
        }
        while ( !q.empty( ) ) 
        {
            int k = q.front( ) ; q.pop( ) ; 
            vis[ trie[ k ].back ] = trie[ k ].ans ; 
            int y = trie[ k ].fail ; in[ y ] -- ; 
            trie[ y ].ans += trie[ k ].ans ; 
            if( !in[ y ] ) q.push( y ) ; 
        }
    }
    void Clear_Tire( )
    {
        numbol = 1 ; 
        memset( Map , 0 , sizeof( Map ) ) ; 
        memset( in , 0 , sizeof( in ) ) ; 
        memset( vis , 0 , sizeof( vis ) ) ; 
        memset( use , 0 , sizeof( use ) ) ; 
        for( int i = 1 ; i < N ; ++ i )
        {
            trie[ i ].fail = 0 ; 
            trie[ i ].back = 0 ; 
            trie[ i ].ans = 0 ; 
            for ( int j = 0 ; j < 26 ; ++ j )
            {
                trie[ i ].son[ j ] = 0 ; 
            }
        }
    }
} tree ; 
int n ; 
signed main( )
{
    cin >> t ; 
    while ( t -- )
    {
        tree.Clear_Tire( ) ; 
        cin >> n ; 
        //cout << 1 << '\n' ; 
        int len ; 
        for ( int i = 1 ; i <= n ; ++ i )
        {
            cin >> s + 1 ; 
            len = strlen( s + 1 ) ; 
            tree.insert( s , len , i ) ;  
        }
        tree.Get_fail( ) ; 
        cin >> Che + 1 ; 
        len = strlen( Che + 1 ) ; 
        tree.query( Che , len ) ; 
        tree.Topu( ) ; 
        int answer = 0 ; 
        for( int i = 1 ; i <= n ; ++ i )
        { 
            if( vis[ Map[ i ] ] )answer ++ ; 
        }
        cout << answer << '\n' ; 
    }
}

· \(AC\) 自动机上跑 \(DP\)

这个...看例题吧。


结尾撒花 \(\color{pink}✿✿ヽ(°▽°)ノ✿\)

标签:AC,int,Fail,son,trie,fail,自动机
From: https://www.cnblogs.com/hangry/p/18018032

相关文章

  • strace df -h
    /proc/self/fd报告进程打开的文件。每个条目都是一个“神奇”的符号链接,其名称是文件描述符,目标是打开的文件。它的神奇之处在于,链接实际上指向文件本身,即使通过调用获得的文件名readlink不是有效的文件名,例如,对于没有名称的文件(例如匿名管道),也会发生这种情况和套接字),并删除文件。......
  • 安卓 adb shell 使用strace
    https://stackoverflow.com/questions/34762544/strace-in-androidhttp://forum.xda-developers.com/showthread.php?t=2516002这个链接里边的下载链接改变内容了,可能域名过期了 https://source.android.com/docs/core/tests/debug/strace?hl=zh-cnmmma-j6external/strace......
  • HackTheBox - Codify [easy]
    打这台靶机时及其古怪。总是莫名其妙断开连接,请求没有响应。提交时表示flag错误等问题访问80端口的web服务,发现使用nodjs和vm2库。搜索到vm2漏洞:SandboxBypassinvm2|CVE-2023-32314|Snyk 可远程执行代码查看当前用户,可登录使用ssh登录,使用linpeas.sh等工具枚举,发......
  • P1217 [USACO1.5] 回文质数 Prime Palindromes
    [USACO1.5]回文质数PrimePalindromes题目描述因为\(151\)既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以\(151\)是回文质数。写一个程序来找出范围\([a,b](5\lea<b\le100,000,000)\)(一亿)间的所有回文质数。输入格式第一行输入两个正整数\(a\)......
  • DaVinci Resolve Studio 18.6.5 (macOS, Windows) - 剪辑、调色、特效和音频后期制作
    DaVinciResolveStudio18.6.5(macOS,Windows)-剪辑、调色、特效和音频后期制作BlackmagicDesignDaVinciResolveStudio请访问原文链接:DaVinciResolveStudio18.6.5(macOS,Windows)-剪辑、调色、特效和音频后期制作,查看最新版。原创作品,转载请保留出处。作者主页......
  • AC自动机
    string  AC自动机是离线型数据结构,所以我们先离线下来所有操作,先建出来AC自动机再对fail树求dfs序用树状数组维护,对fail树的子树区间加为什么是对于子树加呢? 对于fail树的构建我们是由fail[i]$\to$ i 那么也就是说一个节点子树中的点都是代表了一......
  • Tacotron-2 实验记录
    https://blog.csdn.net/u013625492/article/details/100155542TrytheStdVersion1.GetTacotron-2-master.zipfromhttps://github.com/Rayhane-mamah/Tacotron-22.UnzipTacotron-2-master.ziponUnbuntu3.Terminal:cp-rtraining_data./Tacotron-2#training_......
  • AC466A 2024省选联测19 寄(post)
    题意一棵有边权的树,给定\(m\)个关键点,让你选择若干个点,使得每个关键点到你选择的点的距离的最小值之和加上选择的点的个数乘\(C\)最小。求这个最小值。\(n\le3000\)Sol考虑将选择点的个数扔掉,直接考虑对于每个点加上\(C\)的贡献。设\(f_{i,j}\)表示\(i\)的贡献......
  • 阿克曼函数(Ackermann function)部分推导
    相关题目已知\(Ackermannfunction\)为Ack(m,n)={n+1__m=0;Ack(m-1,1)__m>0&&n=0;Ack(m-1,Ack(m,n-1)__m>0&&n>0.}当\(m=1\)时有\(Ack(1,n)\)\(=Ack(0,Ack(1,n-1))=Ack(1,n-1)+1;\)\(=Ack(0,Ack(1,n-2))+1=Ack(1,n-2)+2;\)\(=···\)......
  • Tacotron2语音合成
    Tacotron2语音合成    Tacotron2是由GoogleBrain提出来的一个语音合成框架.模型架构:机器环境:在Ubuntu16.04Ubuntu16.04GPUGeForceRTX2080(单个GPU)TensorFlow1.15cuda10.0cudnn7.6.3下完成.github上有一个Tacotron-2的Tensorflow实现,地址https://github.co......