//hdu2222//AC自动机初学

作者:网络    软件教程库   2020-05-15

// hdu2222 //
#includecstdio
#includecstring
#includecstdlib
#includecmath
#includeiostream
#includealgorithm
#includequeue
using namespace std;
char k[55],s[1000005];
struct node
{
    int fail;
    int next[26];
    int cnt;
    void newnode()
    {
        cnt=0;
        fail=-1;
        for(int i=0;i26;i++)
        {
            next[i]=-1;
        }
    }
}t[500005];
int root=0,tot=0;
void insert(char *str)
{
    int p=root;
    int len=strlen(str);
    for(int i=0;ilen;i++)
    {
        int id=str[i]-‘a‘;
        if(t[p].next[id] == -1)
        {
            t[++tot].newnode();
            t[p].next[id] = tot;
        }
        p = t[p].next[id];
    }
    t[p].cnt++;
}
void build_ac()
{
    queueintq;
    q.push(root);
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=0;i26;i++)
        {
            if(t[p].next[i] != -1)
            {
                q.push(t[p].next[i]);
                if(p==root)
                {
                    t[t[p].next[i]].fail = root;
                }
                else
                {
                    int k = t[p].fail;
                    while(k!=-1)
                    {
                        if(t[k].next[i] != -1)
                        {
                            t[t[p].next[i]].fail = t[k].next[i];
                            break;
                        }
                        k = t[k].fail;
                    }
                    if(k == -1)
                    {
                        t[t[p].next[i]].fail = root;
                    }
                }
            }
        }
    }
}
int query()
{
    int res=0,len=strlen(s);
    int p=root;
    for(int i=0;ilen;i++)
    {
        int id=s[i]-‘a‘;
        while(t[p].next[id] == -1  p!=root)
        {
            p = t[p].fail;
        }
        p = t[p].next[id];
        if(p==-1)
        {
            p=root;
        }
        int k=p;
        while(k!=root  t[k].cnt0)
        {
            res+=t[k].cnt;
            t[k].cnt=-1;
            k = t[k].fail;
        }
    }
    return res;
}
int main()
{
    int t;
    scanf("%d",t);
    while(t--)
    {
        int n;
        scanf("%d",n);
        tot=0;
        t[root].newnode();
        for(int i=1;i=n;i++)
        {
            scanf("%s",k);
            insert(k);
        }
        build_ac();
        scanf("%s",s);
        printf("%d\n",query());
    }
    return 0;
}

// hdu2222 // ac自动机初学

原文地址:http://www.cnblogs.com/wikioibai/p/4471482.html

软件教程库 该篇文章地址:https://www.itjcku.com/9999/1091425.html

阅读全部内容


Tags:自动机初学

返回首页



推荐内容

黑书笔记

就从p77开始记好了.(稍微扩容) p77 排序. 1.香农信息论 基于比较的排序不可能突破o(nlogn)的复杂度限制 ...

//codeforces471D//kmp初学

// codeforces 471d // #includelt;cstdiogt; #includelt;cstrin ...

搭建基于域名虚拟主机

修改主配置文件 # cd /etc/httpd/conf.d/ # vim vhost.conf lt;virtu ...

Mysql5.6.24zip解压缩版配置及修改默认编码方法

win64位下载地址: http://dev.mysql.com/downloads/file.phpid=456319 ...

图片的预加载和按需加载

图片预加载 lt;!doctype htmlgt; lt;htmlgt; lt;headgt; lt;meta htt ...

iPhone/iPad程序怎么禁止自动休眠

//禁止自动休眠可以通过这一句话搞定:[uiapplication sharedapplication].idletim ...

普林斯顿《算法II》第一周学习笔记UndirectedGraph

普林斯顿的算法课是cousera上评价挺高的一门课,课程的教学语言用的是java,课程中的算法都会被封装成类的形式,对于 ...

headFirst学习笔记之九:迭代器与组合模式(5.1)

1.任务: 大新闻!对象村餐厅和对象村煎饼屋合并了!可以在同一个地方吃早饭和午饭了hohoho(有什么好开森的对象村的小 ...

IOSapplicationWillResignActive

一、挂起当有电话进来或者锁屏,这时你的应用程会挂起,在这时,uiapplicationdelegate委托会收到通知,调 ...

哥我要向前看了

七年前的五一节前的那个周六,我遇到生命中一个重要的人。虽然相处短暂,好梦不长,但是回忆丰满,念念不忘。 七年后的五一节, ...

GoldSmith第二章

uhf:特高频 300m-3000mhz shf:超高频 3g-30g 所有发射与接收的信号都是实信号(因为调制器的振荡 ...

动态规划总结【模板】

最长递增子序列 给定一个序列,找到最长子序列的长度,使得子序列中的所有元素被排序的顺序增加。 1.求最长递增子序列的 ...

HDUACM1103Flo'sRestaurant

分析:借助stl的min_element实现。每次更新最先被占用的桌子,具体见注释。 #includelt;iostre ...

【翻译自mos文章】Oracledb12c中,每次日志切换时,会改变alert_sid.log的权限

12c中,每次日志切换时,会改变alert_sid.log的权限 来源于: alert log file‘s perm ...

poj1988(并查集)

题意:有30000个木块,编号从1到30000,然后有两种操作m a b,把木块a所在的堆块放到木块b所在的堆块上,操作 ...

org.hibernate.exception.GenericJDBCException:Couldnotopenconnection

1、错误描述 org.hibernate.exception.genericjdbcexception: could ...

ubuntu下mysql导出数据

使用的是workbench,原因时workbench的导出工具mysqldump和mysql的版本不一致,这个时候手动指 ...

怎样看懂女人哪些最直接的肢体暗示,撒娇

主动拥抱。 拥抱是最简单却十分亲密的身体接触,女人在想亲热时,会主动寻求拥抱,向伴侣靠近。如果她躺在你的怀抱中,并用语言 ...

移动后端云平台Bmob介绍

对于移动端的独立开发者来说,最痛苦的事情莫过于搭建后台服务器。没有基础的还得从头学起,有技术的又要搭建维护后台,非常 ...

WAMP配置虚拟主机

问题背景:从网上下载了一个php项目a,a项目需要部署在网站的根目录下。配置虚拟主机可以解决这个问题。1.打开apach ...

java克隆测试

1.person类 1 //clone方法必须实现cloneable接口 2 public class perso ...

C++string中用于查找的find系列函数浅析

总述:以下所讲的所有的string查找函数,都有唯一的返回类型,那就是size_type,即一个无符号整数(按打印出来的 ...

Savingoutputofagrepintoafilewithcolors

19 down vote favorite 7 i need to save the result o ...

hibernate异常之QueryException

org.hibernate.queryexception: expected positional parameter ...

Redis的Python客户端redis-py的初步使用

1. 安装 sudo pip install redis sudo pip install hiredis pa ...

《构建高性能Web站点》笔记

书名:构建高性能web站点 出版社: 电子工业出版社 isbn:9787121170935 一 绪论 等待的时间: ( ...

制作OSX10.10.3启动安装U盘

1.获得install os xyosemite.app 2.准备一个8gb的u盘,用磁盘工具抹掉,格式默认的mac o ...

域名解析URL转发

url转发 转发功能:如果您没有一台独立的服务器(也就是没有一个独立的ip地址)或者您还有一个域名b,您想访问a域名时访 ...

instancetypeVSid

英文好的直接读下面链接的文章就好了: http://stackoverflow.com/questions/897222 ...

androidapp开发感想

这几天帮学长做app的时候,照着视频学了json数据的传递,接着遇到了问题,就是httpurlconnection会 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com