AC自动机&后缀自动机

理解的不够深 故只能以此来加深理解 。我这个人就是蠢没办法 学长讲的题全程蒙蔽。可能我字符串就是菜吧,哦不我这个人就是菜吧。

AC自动机的名字 AC 取自一个大牛 而自动机就比较有讲究了 不是寻常的东西呢。

自动机由5部分组成 1 字符集 2 状态集合 3 初始状态 4 结束状态集合 5 状态转移函数。

字符集 是指自动机字符的集合。 当然以上有点深奥,我们只需要其能识别字符串即可。

显然的是 KMP做单字符串对单字符串的匹配使用 而AC自动机则是多个字符串在一个字符串上的匹配。

构建trie 大家都会 但是如何求fail 指针呢 思考一下我们求的fail指针其实是指向和当前这个串能匹配的最长后缀。前缀是没有必要的因为我是利用答案串进行匹配的,因为我们得到一个最长前缀再继续这样匹配还是一样效果我们既然答案串都匹配到了现在 也就是当前局面已经不可逆了我们只能不断的跳 跳到一个合法地方让其能继续匹配下去 所以跳到一个最长后缀的位置这样如果还失配的话我们还有机会继续跳 如果跳到一个较短的后缀上的话我们把那些长的都扔了这显然是非常不好做法。

那么现在就有了基础思路构造fail指针 然后失配就不断跳 就行了。在构造fail指针的时候我们是先构造了一颗trie树在trie树搞fail指针显然最长后缀<当前匹配的位置 至于那些比当前位置还要深的位置一定不可能出现,那么就是看深度咯 bfs逐层扩展的过程中 沿着父亲的fail指针走即可。

//#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<algorithm>
#include<vector>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#define INF 1000000000
#define ll long long
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define RI register ll
#define db double
#define EPS 1e-8
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf))+fread(buf,1,1<<15,stdin),fs==ft)?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
const int MAXN=1000010;
char a[MAXN];
int n,root,len,cnt,T,h,ans;
int t[MAXN][26],e[MAXN];
int q[MAXN],fail[MAXN];
inline void insert(char *c)
{
    int p=root;
    //cout<<c[1]<<‘ ‘<<c[2]<<endl;
    for(int i=1;i<=len;++i)
    {
        int w=c[i]-‘a‘;
        if(!t[p][w])t[p][w]=++cnt;
        p=t[p][w];
    }
    ++e[p];
}
inline void get_fail()
{
    T=h=0;
    for(int i=0;i<=25;++i)
    {
        if(t[root][i])
        {
            q[++T]=t[root][i];
            fail[t[root][i]]=0;
        }
    }
    while(h++<T)
    {
        int tn=q[h];
        for(int i=0;i<=25;++i)
        {
            if(t[tn][i])
            {
                q[++T]=t[tn][i];
                fail[t[tn][i]]=t[fail[tn]][i];
            }
            else t[tn][i]=t[fail[tn]][i];
        }
    }
}
inline void AC()
{
    int p=root;
    for(int i=1;i<=len;++i)
    {
        int c=a[i]-‘a‘;
        int w=t[p][c];
        p=t[p][c];
        while(w&&e[w]!=-1)
        {
            ans+=e[w];
            e[w]=-1;
            w=fail[w];
        }
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",a+1);
        len=strlen(a+1);
        insert(a);
    }
    get_fail();
    scanf("%s",a+1);
    len=strlen(a+1);
    AC();
    printf("%d",ans);
    return 0;
}

自己的第二份AC自动机代码这次真的是理解了 因为后缀数组后缀自动机把我搞自闭了。

//#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<algorithm>
#include<vector>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#define INF 1000000000
#define ll long long
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define RI register ll
#define db double
#define EPS 1e-8
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf))+fread(buf,1,1<<15,stdin),fs==ft)?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
const int MAXN=2000010;
char a[MAXN];
int n,root,len,cnt,T,h;
int t[MAXN][26],vis[MAXN];
int q[MAXN],fail[MAXN],ans[MAXN];
inline void insert(char *c,int v)
{
    int p=root;
    //cout<<c[1]<<‘ ‘<<c[2]<<endl;
    for(int i=1;i<=len;++i)
    {
        int w=c[i]-‘a‘;
        if(!t[p][w])t[p][w]=++cnt;
        p=t[p][w];
    }
    vis[v]=p;
}
inline void get_fail()
{
    T=h=0;
    for(int i=0;i<=25;++i)
    {
        if(t[root][i])
        {
            q[++T]=t[root][i];
            fail[t[root][i]]=0;
        }
    }
    while(h++<T)
    {
        int tn=q[h];
        for(int i=0;i<=25;++i)
        {
            if(t[tn][i])
            {
                q[++T]=t[tn][i];
                fail[t[tn][i]]=t[fail[tn]][i];
            }
            else t[tn][i]=t[fail[tn]][i];
        }
    }
}
inline void AC()
{
    int p=root;
    for(int i=1;i<=len;++i)
    {
        int c=a[i]-‘a‘;
        p=t[p][c];++ans[p];
    }
    for(int i=T;i>=1;--i)ans[fail[q[i]]]+=ans[q[i]];
}
int main()
{
    freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",a+1);
        len=strlen(a+1);
        insert(a,i);
    }
    get_fail();
    scanf("%s",a+1);
    len=strlen(a+1);
    AC();
    for(int i=1;i<=n;++i)printf("%d\n",ans[vis[i]]);
    return 0;
}

发现可以直接AC自动机 然后 树上差分一下即可。

原文地址:https://www.cnblogs.com/chdy/p/11173841.html

时间: 07-11

AC自动机&后缀自动机的相关文章

后缀自动机(SAM)学习指南

*在学习后缀自动机之前需要熟练掌握WA自动机.RE自动机与TLE自动机* 什么是后缀自动机 后缀自动机 Suffix Automaton (SAM) 是一个用 O(n) 的复杂度构造,能够接受一个字符串所有后缀的自动机. 它最早在陈立杰的 2012 年 noi 冬令营讲稿中提到. 在2013年的一场多校联合训练中,陈立杰出的 hdu 4622 可以用 SAM 轻松水过,由此 SAM 流行了起来. 一般来说,能用后缀自动机解决的问题都可以用后缀数组解决.但是后缀自动机也拥有自己的优点. 1812.

后缀自动机专题

如果不算pre指针的话后缀自动机就是一个DAG,这是它能很方便地进行dp的前提. 而pre指针返回什么呢,返回的就是上一个的前缀包含改结点所代表子串的那个后缀,和AC自动机上的fail指针很像,都是为了匹配.我目前学得不深,看不出和AC自动机的fail指针有什么区别,用起来也几乎一样. 相比于字典树和回文树,后缀自动机每个结点会有多个父结点,可以表示多种子串(从根节点到它的每条路径都是一个子串),因此子串的信息只能在路径中记录,比如长度,而该子串说记录的长度step,则是根结点到它的最远距离,而

[转]后缀自动机

原文地址:http://blog.sina.com.cn/s/blog_8fcd775901019mi4.html 感觉自己看这个终于觉得能看懂了!也能感受到后缀自动机究竟是一种怎样进行的数据结构了... 笔者自己的话会用楷体表示出来...[说不定能帮助大家理解,但是可能也破坏了大家的自主理解力?所以...看不懂的话再来看好咯...] 常用的字符串处理工具: 1.       整词索引:排序+二分:Hash表.可以解决整词匹配,但不支持前缀搜索:Hash表在模式串定长的情况下可以用RK解决多模式

hdu 4622 Reincarnation(后缀数组|后缀自动机|KMP)

Reincarnation Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 2138    Accepted Submission(s): 732 Problem Description Now you are back,and have a task to do: Given you a string s consist of lo

hihocoder #1465 : 后缀自动机五&#183;重复旋律8

#1465 : 后缀自动机五·重复旋律8 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一段音乐旋律可以被表示为一段数构成的数列. 小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”. 小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品.对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多

HDOJ 5343 MZL&#39;s Circle Zhou 后缀自动机

对第二个串建SAM求出第二个串的以每个字符开头的不同子串的数目.. 再对第一个串建SAM,遍历自动机如果某个节点后面没有某个字符则答案加上这个节点的出现次数乘上以这个字符为开头的在第二个串中的不同子串的数目.. MZL's Circle Zhou Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 244    Accepted Sub

【后缀自动机】资料+个人见解

[资料] 后缀自动机实质上是字母树,记录的字符串是某个字符串s的所有后缀.这里以字符串ACADD为例: 这样很浪费空间和时间(实际上都是O(n^2)).但是,注意:这棵字母树的结点虽然多,但大部分结点都只有一个儿子,而且有很多段是一样的.那么,利用公共部分,就可以对空间进行压缩,具体地说,就是把自己连到儿子的边删掉(并把该儿子及其后代删掉),再把这条边连到别的子树,这样就能充分利用公共部分,节省空间.但是,如何保证这样做和原来的笨做法是等价的,又如何把时间复杂度和空间复杂度降到O(n)?这是个问

【BZOJ3926】【Zjoi2015】诸神眷顾的幻想乡 广义后缀自动机

链接: #include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/44891009"); } 题意.题解.数据.出题人标程 http://wjmzbmr.com/archives/zjoi-2015-day-1%e9%a2%98%e8%a7%a3/26 本蒟蒻的题解: 首先我们发现叶子节点很少,所以可

hiho一下第128周 后缀自动机二&#183;重复旋律5

#1445 : 后缀自动机二·重复旋律5 时间限制:10000ms 单点时限:2000ms 内存限制:512MB 描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一个音乐旋律被表示为一段数构成的数列. 现在小Hi想知道一部作品中出现了多少不同的旋律? 解题方法提示 输入 共一行,包含一个由小写字母构成的字符串.字符串长度不超过 1000000. 输出 一行一个整数,表示答案. 样例输入 aab 样例输出 5 解题方法提示 小Hi:本周的题目其实就是给定一个字符串S,要求出S的所有不同子串的数

后缀自动机总结

后缀自动机是一种确定性有限自动机(DFA),它可以且仅可以匹配一个给定串的任意后缀. 构造一个可以接受一个给定串的所有后缀的不确定性有限自动机(NFA)是很容易的,我们发现我们用通用的将NFA转换成对应DFA的算法转换出来的DFA的状态数都很小(O(n)级别的,远远达不到指数级别).于是,人们就开始研究这种特殊的NFA,并提出了在线增量算法,用O(n)的时间复杂度构造该NFA的DFA.在转换过程中,DFA中对应的NFA中的状态集合其实就是我们的right集合.——————以上在胡扯———————