hdu2222 Keywords Search(ac自动机模板-kuangbin)
程序员文章站
2022-07-03 09:10:35
Keywords Search题目大意:给定T组数据,首先是n个字符串,然后给定一段字符串,问这一段中出现过多少个前面的字符串。思路:很显然这是一个ac自动机的模板题,即给定n个子串然后拿一个比较长的主串进行匹配,当然要注意的是前面的n个字串可能有重复的,要单独处理。Code:kuangbin大神的代码模板真好用#include #include #include #include
Keywords Search
题目大意:
给定T组数据,首先是n个字符串,然后给定一段字符串,问这一段中出现过多少个前面的字符串。
思路:
很显然这是一个ac自动机的模板题,即给定n个子串然后拿一个比较长的主串进行匹配,当然要注意的是前面的n个字串可能有重复的,要单独处理。
Code:kuangbin大神的代码模板真好用
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define INT 9654234
using namespace std;
const int maxn = 500010;
struct Trie{
int next[maxn][26],fail[maxn],end[maxn];
int root,l;
int newnode(){
for(int i=0;i<26;i++) next[l][i]=-1;
end[l++]=0;
return l-1;
}
void init(){
l=0;
root =newnode();
}
void insert(char buf[]){
int len=strlen(buf);
int now=root;
for(int i=0;i<len;i++){
if(next[now][buf[i]-'a']==-1)
next[now][buf[i]-'a']=newnode();
now=next[now][buf[i]-'a'];
}
end[now]++;
}
void bulid(){
queue<int> q;
fail[root]=root;
for(int i=0;i<26;i++){
if(next[root][i]==-1) next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now= q.front();
q.pop();
for(int i=0;i<26;i++){
if(next[now][i]==-1) next[now][i]=next[fail[now]][i];
else{
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
int query(char buf[]){
int len=strlen(buf);
int now=root;
int res=0;
for(int i=0;i<len;i++){
now=next[now][buf[i]-'a'];
int temp=now;
while(temp!=root){
res+=end[temp];
end[temp]=0;
temp=fail[temp];
}
}
return res;
}
void debug(){
for(int i=0;i<l;i++){
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j=0;j<26;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
}
} ac;
char buf[maxn<<1];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T,n;
cin>>T;
while(T--){
cin>>n;
ac.init();
for(int i=1;i<=n;i++){
cin>>buf;
ac.insert(buf);
}
ac.bulid();
cin>>buf;
cout<<ac.query(buf)<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_43872264/article/details/107418015
推荐阅读
-
hdu2222 Keywords Search(ac自动机模板-kuangbin)
-
AC自动机 #10057. 「一本通 2.4 例 1」Keywords Search
-
HDU2222 AC自动机 入门模板
-
hdu2222 Keywords Search(ac自动机模板-kuangbin)
-
HDUOJ 2222 Keywords Search(AC自动机)
-
Keywords Search(AC自动机板子题)
-
【AC自动机】Keywords Search
-
Keywords Search(AC自动机)
-
HDU 2222 Keywords Search AC自动机 Fail数组详解
-
【HDU2222 Keywords Search】AC自动机 | Trie | fail链 | E