AC自动机2
2024-09-05 18:17:24
给N个模式串,求文本串中出现次数最多的模式串出现次数。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define maxm 28
struct AC
{
int trieN;
int ch[maxn][maxm];
int val[maxn];
int fail[maxn];
int s[maxn];
int tim[maxn];
void init()
{
trieN=-;
newnod();
}
int newnod()
{
memset(ch[++trieN],,sizeof ch[]);
val[trieN]=fail[trieN]=;
tim[trieN]=s[trieN]=;
return trieN;
}
void insert(const string & str,int k)
{
int cur=;
for(int i=; i<str.size(); i++)
{
int d=str[i]-'a';
if(!ch[cur][d])
{
ch[cur][d]=newnod();
}
cur=ch[cur][d];
}
val[cur]++;
s[cur]=k;
}
void build()
{
queue<int> q;
for(int i=; i<maxm; i++)
{
if(ch[][i])
{
q.push(ch[][i]);
}
}
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=; i<maxm; i++)
{
if(ch[cur][i])
{
fail[ch[cur][i]]=ch[fail[cur]][i];
q.push(ch[cur][i]);
}
else
{
ch[cur][i]=ch[fail[cur]][i];
}
}
}
}
vector<int>ans;
int man=;
void query(const string & str)
{
ans.clear();
man=;
int res=,cur=;
for(int i=; str[i]; i++)
{
int d=str[i]-'a';
cur=ch[cur][d];
int tmp=cur;
// int si=0;
//cout<<tmp<<'\n';
while(tmp&&val[tmp]>=)
{
res=val[tmp];
if(val[tmp])
{
tim[tmp]++;
if(tim[tmp]>man)
{
man=tim[tmp];
ans.clear();
for(int _i=; _i<res; _i++)
ans.push_back(s[tmp]);
}
else if(man==tim[tmp])
{
for(int _i=; _i<res; _i++)
ans.push_back(s[tmp]);
}
}
//val[tmp]=-1;
tmp=fail[tmp];
} }
}
} ac;
string A[maxn];
int main()
{
string s;
int n;
while(scanf("%d",&n))
{
ac.init();
if(n==)break;
for(int i=; i<n; i++)
{
cin>>A[i];
ac.insert(A[i],i);
}
ac.build();
cin>>s;
ac.query(s);
cout<<ac.man<<'\n';
sort(ac.ans.begin(),ac.ans.end());
for(int i=; i<ac.ans.size(); i++)
{
cout<<A[ac.ans[i]]<<'\n';
}
}
}
最新文章
- kali linux下的arp攻击
- Windows DOS 窗口设置字体颜色
- 装逼名词 bottom-half,软中断,preemptive选项
- java Resource
- php中如何防止表单的重复提交
- Jquery图片放大镜
- Python 一路走来 DOM &; Jquery
- spring 入门篇
- bjective-C 中核心处理字符串的类是 NSString 与 NSMutableString
- Linux安装redis及redis的php扩展。
- 「七天自制PHP框架」第二天:模型与数据库
- CentOSv6.8 修改防火墙配置、修改SSH端口
- python基础8之自定义模块、if __name__==__main__:解释
- 【ASP.NET Core】如何隐藏响应头中的 “Kestrel”
- angularjs兼容thickbox 插件
- VS启动调试速度异常的缓慢问题
- 【HNOI 2018】道路
- Eclipse快捷键大全,导包快捷键:ctrl+Shift+/【转】
- POJ3279(KB1-D 熄灯问题)
- JavaScript匿名函数和回调函数