AC自动机例题
2024-08-28 09:09:42
P3808 [模板]AC自动机(简单版)
[题目描述]
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}
const int MAXN=1e6+5;
const int MAXV=26;
namespace ACzdj{
struct Trie{
int v[MAXV];
int fail,end;
}AC[MAXN];
int Ncnt;
inline void build(string s){
int cur=0,l=s.length();
for(int i=0;i<l;i++){
if(!AC[cur].v[s[i]-'a'])
AC[cur].v[s[i]-'a']=++Ncnt;
cur=AC[cur].v[s[i]-'a'];
}
AC[cur].end+=1;
}
inline void Get_fail(){
queue <int> q;
for(int i=0;i<26;i++)
if(AC[0].v[i]){
AC[AC[0].v[i]].fail=0;
q.push(AC[0].v[i]);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(AC[u].v[i]){
AC[AC[u].v[i]].fail=AC[AC[u].fail].v[i];
q.push(AC[u].v[i]);
}
else
AC[u].v[i]=AC[AC[u].fail].v[i];
}
}
}
inline int query(string s){
int res=0;
int l=s.length(),cur=0;
for(int i=0;i<l;i++){
cur=AC[cur].v[s[i]-'a'];
for(int t=cur;t&&AC[t].end!=-1;t=AC[t].fail){
res+=AC[t].end;
AC[t].end=-1;
}
}
return res;
}
}using namespace ACzdj;
int n;
string s;
int main(){
n=read();
for(int i=1;i<=n;i++){
cin>>s;
build(s);
}
AC[0].fail=0;
Get_fail();
cin>>s;
printf("%d\n",query(s));
}
P3796 [模板]AC自动机(加强版)
[题目描述]
有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}
const int MAXN=150000;
const int MAXM=155;
const int MAXV=26;
struct Node{
int num,id;
friend bool operator < (Node a,Node b){
if(a.num==b.num) return a.id<b.id;
return a.num>b.num;
}
}ans[MAXM];
namespace ACzdj{
struct Trie{
int v[MAXV];
int fail,end;
}AC[MAXN];
int Ncnt;
inline void clear(int x){
for (register int i = 0; i < 26; ++i)
AC[x].v[i] = 0;
AC[x].fail=0,AC[x].end=0;
}
inline void build(const string& s,int id){
int cur=0,l=s.length();
for(int i=0;i<l;i++){
if(!AC[cur].v[s[i]-'a']){
AC[cur].v[s[i]-'a']=++Ncnt;
clear(Ncnt);
}
cur=AC[cur].v[s[i]-'a'];
}
AC[cur].end=id;
}
inline void Get_fail(){
queue<int> q;
for(int i=0;i<26;i++)
if(AC[0].v[i]){
AC[AC[0].v[i]].fail=0;
q.push(AC[0].v[i]);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(AC[u].v[i]){
AC[AC[u].v[i]].fail=AC[AC[u].fail].v[i];
q.push(AC[u].v[i]);
}
else
AC[u].v[i]=AC[AC[u].fail].v[i];
}
}
}
inline void query(const string& s){
int l=s.length(),cur=0;
for(int i=0;i<l;i++){
cur=AC[cur].v[s[i]-'a'];
for(int t=cur;t;t=AC[t].fail)
ans[AC[t].end].num++;
}
}
}using namespace ACzdj;
int n;
string s[MAXM];
int main(){
// freopen("trie.in","r",stdin);
// freopen("trie.out", "w", stdout);
while(n = read()){
clear(Ncnt=0);
for(int i=1;i<=n;i++){
cin>>s[i];
ans[i].num=0,ans[i].id=i;
build(s[i],i);
}
AC[0].fail=0;
Get_fail();
cin>>s[0];
query(s[0]);
sort(ans+1,ans+n+1);
printf("%d\n",ans[1].num);
cout<<s[ans[1].id]<<endl;
for(int i=2;ans[i].num==ans[i-1].num&&i<=n;i++)
//printf("%s\n",s[ans[i].id]);
cout<<s[ans[i].id]<<endl;
}
}
最新文章
- jQuery静态方法globalEval使用和源码分析
- eclipse+SVN文件只显示版本号，不显示时间和作者解决办法
- 解决java中对URL编码的问题
- js获取某个标签中的信息
- Tomcat7.0.22在Windows下详细配置过程
- 前端学习笔记(zepto或jquery)——对li标签的相关操作（一）
- 多线程简介及GCD的使用
- yii2 邮件发送
- Beta开始前准备
- SQL Sever 2012版本数据库的完全安装流程
- ceph删除pool提示（you must first set the mon_allow_pool_delete config option to true）解决办法
- dubbo源码分析13——服务本地暴露 exportLocal(url)
- KenBurns特效组件KenBurnsView
- JavaScript高级程序设计学习(四)之引用类型
- 移除list中null元素
- 自建mail服务器之一：dns解析
- @JsonInclude注解，RestTemplate传输值为null的属性，利用FastJson将属性中有空值null的对象转化成Json字符串
- ORM数据库框架 SQLite 常用数据库框架比较 MD
- VMware的存储野心(上):软件定义、分布式DAS支持
- （原+译）pytorch中保存和载入模型