文档章节

Codeforces963C Frequency of String 【字符串】【AC自动机】

o
 osc_z1hvg4cu
发布于 2018/04/24 21:24
字数 649
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目大意:

  给一个串s和很多模式串,对每个模式串求s的一个最短的子串使得这个子串中包含至少k个该模式串。

题目分析:

  均摊分析,有sqrt(n)种长度不同的模式串,所以有关的串只有msqrt(n)种。暴力用AC自动机找出来即可。

代码:

  

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn = 102000;
  5 const int sigma = 26;
  6 
  7 int n,num,root,d[maxn],fa[maxn],fail[maxn],Ex[maxn];
  8 string str,query[maxn];
  9 vector<int> ans[maxn];
 10 
 11 int Number(char ch){return (int)(ch-'a');}
 12 
 13 struct trie{int data,end,nxt[sigma];}T[maxn];
 14 
 15 void insert(int now,int pla,int tnode){
 16     if(pla == query[now].size()){T[tnode].end=now;return;}
 17     int p = Number(query[now][pla]);
 18     if(T[tnode].nxt[p]){insert(now,pla+1,T[tnode].nxt[p]);}
 19     else{
 20     num++;T[tnode].nxt[p] = num;T[num].data = p;
 21     fa[num] = tnode; insert(now,pla+1,num);
 22     }
 23 }
 24 
 25 void read(){
 26     cin >> str >> n;
 27     for(int i=1;i<=n;i++){
 28     cin >> d[i] >> query[i];
 29     insert(i,0,root);
 30     }
 31 }
 32 
 33 queue <int> q;
 34 void BuildAC(){
 35     for(int i=0;i<sigma;i++) if(T[root].nxt[i]) q.push(T[root].nxt[i]);
 36     while(!q.empty()){
 37     int k = q.front();q.pop();
 38     int hh = fail[fa[k]];
 39     while(hh != root){
 40         if(T[hh].nxt[T[k].data]){fail[k]=T[hh].nxt[T[k].data];break;}
 41         else hh = fail[hh];
 42     }
 43     if(T[hh].nxt[T[k].data]&&(!fail[k])&&T[hh].nxt[T[k].data]!=k){
 44         fail[k]=T[hh].nxt[T[k].data];
 45     }
 46     for(int i=0;i<sigma;i++) if(T[k].nxt[i]) q.push(T[k].nxt[i]);
 47     }
 48 }
 49 
 50 void BuildExtraFail(){
 51     q.push(root);
 52     while(!q.empty()){
 53     int k = q.front();q.pop();
 54     int hh = fail[k];
 55     if(T[hh].end){Ex[k] = hh;}else Ex[k] = Ex[hh];
 56     for(int i=0;i<sigma;i++) if(T[k].nxt[i]) q.push(T[k].nxt[i]);
 57     }
 58 }
 59 
 60 void RunAC(){
 61     int now = root;
 62     for(int i=0;i<str.length();i++){
 63     int p = Number(str[i]);
 64     if(T[now].nxt[p]) now = T[now].nxt[p];
 65     else{
 66         int hh = fail[now];
 67         int fg = false;
 68         while(hh != root){
 69         if(T[hh].nxt[p]){fg=1;now=T[hh].nxt[p];break;}
 70         else hh = fail[hh];
 71         }
 72         if(fg == 1)goto loop;
 73         if(T[hh].nxt[T[p].data])now=T[hh].nxt[T[p].data];
 74         else now = root;
 75     }
 76     loop:int z = Ex[now];
 77     if(T[now].end) ans[T[now].end].push_back(i);
 78     while(z!=root){ans[T[z].end].push_back(i);z=Ex[z];}
 79     }
 80 }
 81 
 82 int Min(int a,int b){return a<b?a:b;}
 83 
 84 void work(){
 85     BuildAC();
 86     BuildExtraFail();
 87     RunAC();
 88     for(int i=1;i<=n;i++){
 89     if(ans[i].size()<d[i]){cout<<-1<<endl;continue;}
 90     int minn = 123456789;
 91     for(int j=d[i]-1;j<ans[i].size();j++){
 92         minn = Min(minn,ans[i][j]-ans[i][j-d[i]+1]+query[i].length());
 93     }
 94     cout<<minn<<endl;
 95     }
 96 }
 97 
 98 int main(){
 99     read();
100     work();
101     return 0;
102 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Android FM模块学习之四源码分析(八)

接上一篇 ,今天将要来看看androidvendorqcomopensourcefmfmapp2srccomcaffmradio PresetStation.java 调整频率位置状态构造方法 public PresetStation(String name, int frequency) { mName......

天王盖地虎626
2019/01/08
10
0
Java实现哈夫曼编码和解码

最近无意中想到关于api返回值加密的问题,譬如我们的api需要返回一些比较敏感或者重要不想让截获者得到的信息,像如果是做原创图文的,文章明文返回的话则有可能被抓包者窃取。 关于请求时加...

tianyaleixiaowu
07/06
0
0
451. Sort Characters By Frequency。

Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: “tree” Output: “eert” Explanation: ‘e’ appears twice while ‘r’ and ‘......

leafage_m
2018/02/25
0
0
WordCount小组作业——WordCount类

基本任务 1.Github项目地址 https://github.com/LXL1314/WordCount 2.PSP表格填写 PSP2.1 PSP阶段 预估耗时 (分钟) 实际耗时 (分钟) Planning 计划 20 20 Estimate 估计这个任务需要多少...

osc_bfhs2jat
2018/04/08
0
0
451. Sort Characters By Frequency。

版权声明:本文为博主原创文章,转载请标明出处:http://blog.csdn.net/leafagem https://blog.csdn.net/LeafageM/article/details/79370857 Given a string, sort it in decreasing order b......

繁城落叶
2018/02/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud开发人员如何解决服务冲突和实例乱窜?(IP实现方案)

点击上方“陶陶技术笔记”关注我 回复“资料”获取作者整理的大量学习资料! 一、背景 在我上一篇文章《Spring Cloud开发人员如何解决服务冲突和实例乱窜?》中提到使用服务的元数据来实现隔...

zlt2000
2019/09/06
0
0
Linux下diff命令用法详解

大家好,我是良许。 我们在平时工作的时候,经常要知道两个文件之间,以及同个文件不同版本之间有何异同点。在 Windows 下,有 beyond compare 这个好用的工具,而在 Linux 下,也有很多很强...

osc_th8jvcw7
32分钟前
7
0
万变不离其宗之UART要点总结

[导读] 单片机开发串口是应用最为广泛的通信接口,也是最为简单的通信接口之一,但是其中的一些要点你是否明了呢?来看看本人对串口的一些总结,当然这个总结并不能面面俱到,只是将个人认为...

osc_kyehmyzk
33分钟前
7
0
kafka的认识、安装与配置

认识Kafka 花费越少的精力在数据移动上,就能越专注于核心业务 --- 《Kafka:The Definitive Guide》 认识 Kafka 之前,先了解一下发布与订阅消息系统:消息的发送者不会直接把消息发送给接收...

osc_wy8nhxhn
35分钟前
0
0
使用pandas进行数据处理——DataFrame篇

  今天是pandas数据处理专题的第二篇文章,我们一起来聊聊pandas当中最重要的数据结构——DataFrame。   上一篇文章当中我们介绍了Series的用法,也提到了Series相当于一个一维的数组,只...

开源仔
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部