AC自动机板子(from. qwer)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int N=510000;
struct Tri
{
    int Next[N][26], fail[N], val[N], root, L;
    void init() {L = 0;root = newnode();}
    int newnode()
    {
        for(int i = 0;i < 26;i++) Next[L][i] = -1;
        val[L++] = 0;
        return L - 1;
    }

    void insert(char s[])
    {
        int len = strlen(s), cur = root;
        for(int i = 0;i < len;i++)
        {
            if(Next[cur][s[i]-‘a‘] == -1)
                Next[cur][s[i]-‘a‘] = newnode();
            cur = Next[cur][s[i]-‘a‘];
        }
        val[cur]++;
    }
    void build()
    {
        queue<int>Q;
        fail[root] = root;
        for(int i = 0;i < 26;i++)
            if(Next[root][i] == -1) Next[root][i] = root;
            else
            {
                fail[Next[root][i]] = root;
                Q.push(Next[root][i]);
            }
        while(!Q.empty())
        {
            int cur = Q.front(); Q.pop();
            for(int i = 0;i < 26;i++)
                if(Next[cur][i] == -1)
                    Next[cur][i] = Next[fail[cur]][i];
                else
                {
                    fail[Next[cur][i]]=Next[fail[cur]][i];
                    Q.push(Next[cur][i]);
                }
        }
    }
    int query(char s[])
    {
        int len = strlen(s), cur = root, res = 0;
        for(int i = 0;i < len;i++)
        {
            cur = Next[cur][s[i]-‘a‘];
            int tmp = cur;
            while (tmp != root)
            {
                res += val[tmp];
                val[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
};
char s[N];
Tri AC;
int n;
int main()
{
      scanf("%d",&n);
      AC.init();
      for(int i = 0;i < n;i++)
      {
          scanf("%s",s);
          AC.insert(s);
      }
      AC.build();
      scanf("%s",s);
      printf("%d\n",AC.query(s));
      return 0;
}
时间: 01-25

AC自动机板子(from. qwer)的相关文章

AC自动机板子

例题:HDU - 2222 给\(n\)个字符串,一个模式串.然后输出匹配次数. 代码 #include <bits/stdc++.h> #define FOPI freopen("in.txt", "r", stdin) #define FOPO freopen("out.txt", "w", stdout) #define FOR(i,x,y) for (int i = x; i <= y; i++) #

AC自动机 板子

https://www.luogu.org/problemnew/show/3808 在Tire上做KMP #include<cstdio> #include<queue> #include<iostream> #define FOR(i,s,t) for(register int i=s;i<=t;++i) using std::cin; const int N=4000011; char s[N]; int tot,n,ans; namespace AC_au

AC自动机总结及板子

蒟蒻最近想学个AC自动机简直被网上的板子搞疯了,随便点开一个都是带指针的,然而平时用到指针的时候并不多,看到这些代码也完全是看不懂的状态.只好在大概理解后自己脑补(yy)了一下AC自动机的代码,居然还过了,这里对学到的东西做一点小小的总结.顺便造福一下跟我之前一样没有学过AC自动机并且不会用指针的Oier,给出一段不带指针的板子. AC自动机的模型很好理解,就是在Trie树上做类似于KMP的操作.所以说在AC自动机里也会有一个类似于 next 数组的东西------ fail 数组来作为失配指针

luogu P3808 【模板】AC自动机(简单版)

二次联通门 : luogu P3808 [模板]AC自动机(简单版) /* luogu P3808 [模板]AC自动机(简单版) 手速越来越快了 10分钟一个AC自动机 一遍过编译 + 一边AC 感觉不错 我也就做做板子题了.. */ #include <iostream> #include <cstring> #include <cstdio> #include <queue> #define Max 1000009 void read (int &

【小结】AC自动机

参考资料:http://blog.csdn.net/niushuai666/article/details/7002823 搞了两天,突然明白,这玩意它原来就是个DFA鸭!窝来分析分析 从DFA到AC自动机: 考虑以下单词: {she, he, her},字母表∑为26个小写字母 我们先画出它Trie树的模样 注意,双圈的是包含单词结尾的位置.然后我们尝试将它稍加改造,变成一个DFA! 对每一个状态,必须补充下一个字母为其它(比如从起始状态出发,输入一个h,匹配上了,接下来输入可能为a-z,我们

AC自动机(简单版)

觉得AC自动机怪简单是怎么回事?(可能题太裸了) 原题链接:https://www.luogu.org/problemnew/show/P3808 网上讲AC自动机和tire树讲的比我好的dalao数不胜数,我就不多赘述了,权当是挂个板子吧. 其实char和strlen还是挺好用的. #include<cstdio> #include<queue> #include<cstring> using namespace std; struct tire { int fail

AC自动机及KMP练习

好久都没敲过KMP和AC自动机了.以前只会敲个kuangbin牌板子套题.现在重新写了自己的板子加深了印象.并且刷了一些题来增加自己的理解. KMP网上教程很多,但我的建议还是先看AC自动机(Trie图)的构造后再去理解.板子的话大家大同小异. 而AC自动机的构造则是推荐王贇的<Trie图的构建.活用与改进>. 前面的备用知识则是字典树.推荐董华星的<浅析字母树在信息学竞赛中的应用>.董聚聚不仅仅是介绍了字典树,包括一些常见的应用也有论述,介绍的挺详细的. 接下来就是刷题的部分了.

AC自动机学习小结

AC自动机 简要说明 \(AC\) 自动机,全称 \(Aho-Corasick\ automaton\) ,是一种有限状态自动机,应用于多模式串匹配.在 \(OI\) 中通常搭配 \(dp\) 食用.因为它是状态自动机. 感性理解:在 \(Trie\) 树上加上 \(fail\) 指针.具体的讲解可以去看dalao们的博客(因为我实在是太菜了讲不好). 题目 Keywords Search 题目:给若干个模式串,再给一个文本串,问有几个模式串在文本串中出现过. 板子题.注意一个模式串只被计算一次

AC自动机初步

概述 应用场景:多模字符串匹配问题. KMP解决的问题是两个字符串之间的互相匹配,而如果有多个字符串要和一个字符串进行匹配呢?如果还用KMP的话,复杂度依然上天,所以,一个正常的想法是在KMP的基础上堆数据结构. 所以AC自动机=在Trie树上跑KMP,它其中也存在失配数组,与KMP类似. 初见 AC自动机的基础是Trie树.和Trie树不同的是,树中的每个结点除了有指向孩子的指针(或者说引用),还有一个fail指针,它表示输入的字符与当前结点的**所有孩子结点都不匹配时**(注意,不是和该结点