hdu 5384 Danganronpa 2015多校联合训练赛#8 ac自动机_danganronpa多校-程序员宅基地

技术标签： ##字符串  ##ACM-ICPC编程题  ACM之数据结构  ACM之2015多校联合训练赛  字符串  2015多校联合训练赛  ac自动机  

Danganronpa 

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 171    Accepted Submission(s): 83

Problem Description
Danganronpa is a video game franchise created and developed by Spike Chunsoft, the series' name is compounded from the Japanese words for "bullet" (dangan) and "refutation" (ronpa).

Now, Stilwell is playing this game. There are  n  verbal evidences, and Stilwell has  m  "bullets". Stilwell will use these bullets to shoot every verbal evidence.

Verbal evidences will be described as some strings  Ai , and bullets are some strings  Bj . The damage to verbal evidence  Ai  from the bullet  Bj  is  f(Ai,Bj) .
f(A,B)=∑i=1|A|−|B|+1[ A[i...i+|B|−1]=B ]
In other words,  f(A,B)  is equal to the times that string  B  appears as a substring in string  A .
For example:  f(ababa,ab)=2 ,  f(ccccc,cc)=4

Stilwell wants to calculate the total damage of each verbal evidence  Ai  after shooting all  m  bullets  Bj , in other words is  ∑mj=1f(Ai,Bj) .
 

Input
The first line of the input contains a single number  T , the number of test cases.
For each test case, the first line contains two integers  n ,  m .
Next  n  lines, each line contains a string  Ai , describing a verbal evidence.
Next  m  lines, each line contains a string  Bj , describing a bullet.

T≤10
For each test case,  n,m≤105 ,  1≤|Ai|,|Bj|≤104 ,  ∑|Ai|≤105 ,  ∑|Bj|≤105
For all test case,  ∑|Ai|≤6∗105 ,  ∑|Bj|≤6∗105 ,  Ai  and  Bj  consist of only lowercase English letters
 

Output
For each test case, output  n  lines, each line contains a integer describing the total damage of  Ai  from all  m  bullets,  ∑mj=1f(Ai,Bj) .
 

Sample Input 
  
  
   

    
   
   1
5 6
orz
sto
kirigiri
danganronpa
ooooo
o
kyouko
dangan
ronpa
ooooo
ooooo
 

Sample Output 
  
  
   

    
   
   1
1
0
3
7
 

Source
2015 Multi-University Training Contest 8


对所有单词建立ac自动机。然后跑一边就完事了。


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
struct Node{
    Node*ch[27],*fail;
    int mark,id;
}word[600001];//´æ×ÖµäÊ÷
int cnt;
Node *super,*root;//
Node*newNode(){//²åÈë×Ö·û´
    memset(&word[cnt],0,sizeof(word[0]));
    word[cnt].id = cnt;
    return &word[cnt++];
}
void insert(Node*root,char*s){//½¨Ê÷
    if(*s==0){
        root->mark++;
        return;
    }
    int id = *s-'a';
    if(root->ch[id] == 0)
        root->ch[id] = newNode();
    insert(root->ch[id],s+1);
}
void build(Node*root){//
    for(int i = 0;i < 27;i++)
        super->ch[i] = root;
    root->fail = super;
    queue<Node*>Q;
    Q.push(root);
    while(!Q.empty()){
        Node* q = Q.front();
        Q.pop();
        for(int i = 0;i < 27; i++){
            if(q->ch[i] != NULL){
                Q.push(q->ch[i]);
                q->ch[i]->fail = q->fail->ch[i];
                q->ch[i]->mark += q->fail->ch[i]->mark;
            }
            else q->ch[i] = q->fail->ch[i];
        }
    }
}
ll autofind(char *s){
    ll ans = 0,id;
    Node*rt = root,*p;
    while(*s){
        id = *s - 'a';
        if(rt->ch[id] != root) rt = rt->ch[id];
        else{
            while(rt != root && rt->ch[id] == root)
            	rt = rt->fail;
        }
        ans += rt->mark;
        s++;
        if(*s == 'a'+26){
            printf("%I64d\n",ans);
            ans = 0;
        }
    }
    return ans;
}

char sen[400007];
char wor[400007];
int main(){
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        cnt = 0;
        scanf("%d%d",&n,&m);
        int len = 0,lex;
        for(int i = 0;i < n; i++){
            scanf("%s",sen+len);
            lex = strlen(sen+len);
            len += lex;
            sen[len] = 'a'+26;
            len++;
        }
        sen[len] = '\0';

        super = newNode();
        root = newNode();
        for(int i = 0;i < m; i++){
            scanf("%s",wor);
            insert(root,wor);
        }
        build(root);
        ll ans = autofind(sen);

        //printf("%I64d\n",ans);
    }
    return 0;
}


版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/firenet1/article/details/47617665

智能推荐

s2 安恒 漏洞验证工具_Struts2 部分漏洞复现-程序员宅基地

文章浏览阅读959次。s2-061已经复现过了，低版本漏洞可以使用k8哥哥和安恒的工具完成检测和写马，就不再做复现了，当然也可以使用漏扫去发现漏洞。s2-059漏洞描述：攻击者可以通过构造恶意的OGNL表达式，并将其设置到可被外部输入进行修改，且会执行OGNL表达式的Struts2标签的属性值，引发OGNL表达式解析，最终造成远程代码执行的影响。影响版本：Struts 2.0.0 – Struts 2.5.2...

ROS踩过的大大小小的坑_[rospack] error: package 'map_server' not found-程序员宅基地

文章浏览阅读1.1k次，点赞3次，收藏3次。首先声明，这些问题都是博主自己在学习ROS的时候，遇到大大小小的坑，想把它写下来，来帮助更多的人，希望别人在学习的时候少走弯路，加油，陌生人。ROS学习常采坑避雷1、在编译mbot_gazebo功能包的时候出现编译错误2、在进行kinect-gazebo仿真的时候，调出Rviz或者是rqt_image_view的时候，gazebo会提示进程被杀死3、在编译gazebo功能包的时候出现编译错误1..._[rospack] error: package 'map_server' not found

JAVA常见基础面试问题汇集_#java基础面试选择题-程序员宅基地

文章浏览阅读2.3w次，点赞77次，收藏344次。1.Java 的多态表现在哪里？多态要有动态绑定,否则就不是多态,方法重载也不是多态(因为方法重载是编译期决定好的,没有后期也就是运行期的动态绑定)多态当满足这三个条件 1.有继承 2. 有重写 3. 要有父类引用指向子类对象2.抽象类与接口的区别（1）一个类只能继承一个抽象类，一个类可以实现多个接口（2）抽象类中可以存在非抽象方法，接口中的方法都是抽象方法（3）抽象类可以有私..._#java基础面试选择题

linux交叉编译头文件,交叉编译头文件位置-程序员宅基地

文章浏览阅读1k次。7th of March 2013头文件的查找方式和库的搜索路径作者：程姚根,华清远见嵌入式学院讲师。对于以压缩包发布的软件，在它的目录下通常都有一个配置脚本configure，它的作用确定编译参数(比如头文件位置、连接库位置等)，然后生成Makefile以编译程序。可以进入该软件的目录，执行"./configure --help"命令查看使用帮。一个程序能正确编译、链接、运行需要满足3个条件：预..._linux内核交叉编译安转头文件

usestate中的回调函数_TypeScript 中使用React Hook-程序员宅基地

文章浏览阅读657次。TypeScript 中使用React Hook从 React V 16.8.0 和 React Native 0.59.0 版本开始, 引入了React Hook的概念。React Hook 在开发支持就考虑到了类型，所以很多Hook函数可以直接推断出他们的参数、返回值等类型，但也有一些场景需要我们显示声明类型。阅读本文前你需要了解React Hook 的基本用法，参考这里。下面会总结一下我们如..._react usestate 回调函数

MapTiler介绍-程序员宅基地

文章浏览阅读7.8k次。maptiler是基于GDAL编写的商业软件（收费），可以进行地图切片和发布，官网https://www.maptiler.com/MapTiler 提供了一套简单的解决方案，用于对任何具备地理参考的地图图像生成切片。这些切片可以用于网络地图服务。MapTiler支持栅格地理数据（TIFF / GeoTIFF，MrSID，ECW，JPEG2000，Erdas HFA，NOAA BSB ..._maptiler

随便推点

ORB_SLAM2 / 视觉SLAM十四讲 中关于Pangolin 版本的问题_ubuntu查看pangolin版本-程序员宅基地

文章浏览阅读5.1k次，点赞5次，收藏45次。图为https://github.com/gaoxiang12/slambook2中ch3/visualizeGeometry/visualizeGeometry.cpp的报错。原因是安装Pangolin时直接git clone https://github.com/stevenlovegrove/Pangolin.git此方法下载的是最新版本的Pangolin（目前是Pangolin0.6）而Pangolin0.6用的是C++17标准编译。而ORB_SLAM2 和 slambook2 的代码_ubuntu查看pangolin版本

主播都在播的王牌战争：代号英雄是款什么样的游戏？王牌战争模拟器电脑版教程-程序员宅基地

文章浏览阅读2.1k次。王牌战争：代号英雄好玩吗？王牌战争：代号英雄吃鸡手游怎么玩？王牌战争：代号英雄是英雄互娱发行的首款生存竞技手游，8v8血存血战百人竞技激战生存吃鸡手游。最近很多主播都在直播一款叫王牌战争：代号英雄的吃鸡手游，那么这款手游到底好不好玩？跟刺激战场和全军出击又有什么区别呢？手机屏幕太小，想在电脑上玩代号英雄怎么操作？游戏优点：1、300M内存，不占用手机配置。当你的手机玩不起荒野行动，玩不...

Vue框架Element UI教程-左侧导航栏（四）-程序员宅基地

文章浏览阅读1.2w次。Element UI手册：https://cloud.tencent.com/developer/doc/1270中文文档：http://element-cn.eleme.io/#/zh-CNgithub地址：https://github.com/ElemeFE/element接前三篇，Vue框架Element UI教程-安装环境搭建（一）htt..._elementui弹框设置导航栏

vue项目图片预览v-viewer插件使用-程序员宅基地

文章浏览阅读1.3w次，点赞3次，收藏19次。前言：项目管理后台有个需求，管理人员可通过点击进行预览用户上传的图片，因产品对预览的样式之类的要求不高，只需能预览、缩小、放大、旋转、显示图片类名等基本功能即可，所以楼主选择v-viewer插件来实现。v-viewer插件链接：https://github.com/mirari/v-viewer#readme安装配置npm install v-viewer --save使用：v-viewer的使用有两种方式，一种是全局使用，直接在main.js中引入，另一种是在要使用的组件引入使用，建议_v-viewer

Java语言学习思维导图_java语句思维导图-程序员宅基地

文章浏览阅读1.8k次，点赞2次，收藏2次。Java语言学习思维导图_java语句思维导图

node vue 实时推送_如何使用Node，Vue和ElasticSearch构建实时搜索引擎-程序员宅基地

文章浏览阅读337次。node vue 实时推送 介绍 (Introduction)Elasticsearch is a distributed, RESTful search and analytics engine capable of solving a growing number of use cases. Elasticsearch is built on top of Apache Lucene, wh..._vue elasticsearch

推荐文章

热门文章

相关标签