当前位置:网站首页>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;
}
边栏推荐
- MySQL常用语句整理
- [TypeScript]OOP
- 动态规划(一)
- 【Yugong Series】July 2022 Go Teaching Course 020-Array of Go Containers
- Go1.18升级功能 - 模糊测试Fuzz 从零开始Go语言
- Small program: Matlab solves differential equations "recommended collection"
- Replication Latency Case (3) - Monotonic Read
- Flutter 获取状态栏statusbar的高度
- IP协议从0到1
- 【pytorch】pytorch 自动求导、 Tensor 与 Autograd
猜你喜欢
【pytorch】1.7 pytorch与numpy,tensor与array的转换
二分查找的细节坑
第05章 存储引擎【1.MySQL架构篇】【MySQL高级】
使用 Postman 工具高效管理和测试 SAP ABAP OData 服务的试读版
C language "the third is" upgrade (mode selection + AI chess)
Automated testing - web automation - first acquaintance with selenium
[pytorch] 1.7 pytorch and numpy, tensor and array conversion
Smart Trash Can (8) - Infrared Tube Sensor (Raspberry Pi pico)
C程序是如何跑起来的01 —— 普通可执行文件的构成
智能垃圾桶(九)——震动传感器(树莓派pico实现)
随机推荐
【pytorch】1.7 pytorch与numpy,tensor与array的转换
牛客 HJ19 简单错误记录
tooltips使用教程(鼠标悬停时显示提示)
【pytorch】pytorch 自动求导、 Tensor 与 Autograd
Stuck in sill idealTree buildDeps during npm installation, npm installation is slow, npm installation is stuck in one place
二分查找的细节坑
Masterless Replication System (3)-Limitations of Quorum Consistency
npm安装时卡在sill idealTree buildDeps,npm安装速度慢,npm安装卡在一个地方不动
LeetCode_733_Image rendering
LeetCode_733_图像渲染
[TypeScript] In-depth study of TypeScript type operations
2.索引及调优篇【mysql高级】
牛客 HJ3 明明的随机数
GP 6 overall architecture study notes
Single-cell sequencing workflow (single-cell RNA sequencing)
6. 使用 Postman 工具高效管理和测试 SAP ABAP OData 服务
使用互相关进行音频对齐
C language - function
软件实现AT命令操作过程
牛客 HJ20 密码验证合格程序