当前位置:网站首页>AcWing 1282. Search Keyword Problem Solution ((AC Automata) Trie+KMP)+bfs)
AcWing 1282. Search Keyword Problem Solution ((AC Automata) Trie+KMP)+bfs)
2022-07-31 16:40:00 【QingQingDE23】
AcWing 1282. 搜索关键词((AC自动机)Trie+KMP)+bfs)
An algorithm that I wanted to learn a long time ago,But I didn't understand it before,Good thing I got it this time
希望ACAutomata can help meAC吧
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, S = 55;
int cnt[N * S], tr[N * S][26], ne[N * S];
int n, T, ids;
int q[N * S];
string str;
void insert(){
int p = 0;
for(int i = 0; str[i]; i ++ ){
int t = str[i] - 'a';
if(!tr[p][t]) tr[p][t] = ++ ids;
p = tr[p][t];
}
cnt[p] ++ ;
}
void build(){
int hh = 0, tt = -1;
for(int i = 0; i < 26; i ++ ){
if(tr[0][i]) q[ ++ tt] = tr[0][i];
}
while(hh <= tt){
int t = q[hh ++ ];
for(int i = 0; i < 26; i ++ ){
int p = tr[t][i];
if(!p) tr[t][i] = tr[ne[t]][i];
else{
ne[p] = tr[ne[t]][i];
q[ ++ tt] = p;
}
}
}
}
int main()
{
cin>>T;
while(T -- ){
cin>>n;
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
memset(tr, 0, sizeof tr);
ids = 0;
int res = 0;
for(int i = 0; i < n; i ++ ){
cin>>str;
insert();
}
build();
cin>>str;
for(int i = 0, j = 0; str[i]; i ++ ){
int t = str[i] - 'a';
j = tr[j][t]; //代表从j节点连到tbranch of node,j是从根节点开始
int p = j;
while(p){
res += cnt[p];
cnt[p] = 0;
p = ne[p];
}
}
cout<<res<<endl;
}
return 0;
}
边栏推荐
- Premiere Pro 2022 for (pr 2022)v22.5.0
- Flutter set the background color of the statusbar status bar and APP method (AppBar) internal consistent color.
- 动态规划之线性dp(下)
- MySQL multi-table union query
- After Effects 教程,如何在 After Effects 中调整过度曝光的快照?
- 牛客 HJ19 简单错误记录
- 【pytorch】pytorch 自动求导、 Tensor 与 Autograd
- 软件实现AT命令操作过程
- LeetCode_733_Image rendering
- Automated testing - web automation - first acquaintance with selenium
猜你喜欢
随机推荐
外媒所言非虚,苹果降价或许是真的在清库存
牛客 HJ3 明明的随机数
牛客网刷题(四)
单细胞测序流程(单细胞rna测序)
牛客 HJ17 坐标移动
【网络通信三】研华网关Modbus服务设置
npm安装时卡在sill idealTree buildDeps,npm安装速度慢,npm安装卡在一个地方不动
js的toString方法
智能垃圾桶(九)——震动传感器(树莓派pico实现)
6-22 Vulnerability exploit - postgresql database password cracking
Applicable Scenarios of Multi-Master Replication (1) - Multi-IDC
[Meetup Preview] OpenMLDB+OneFlow: Link feature engineering to model training to accelerate machine learning model development
认识异常 (看完这篇你就懂了)
Golang——从入门到放弃
Unity 之 图集属性详解和代码示例 -- 拓展一键自动打包图集工具
无主复制系统(2)-读写quorum
adb shell 报错error: device unauthorized
ansible study notes 02
复杂高维医学数据挖掘与疾病风险分类研究
研发过程中的文档管理与工具