AC自动机

给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';
}
}
}

最新文章

  1. kali linux下的arp攻击
  2. Windows DOS 窗口设置字体颜色
  3. 装逼名词 bottom-half,软中断,preemptive选项
  4. java Resource
  5. php中如何防止表单的重复提交
  6. Jquery图片放大镜
  7. Python 一路走来 DOM &amp; Jquery
  8. spring 入门篇
  9. bjective-C 中核心处理字符串的类是 NSString 与 NSMutableString
  10. Linux安装redis及redis的php扩展。
  11. 「七天自制PHP框架」第二天:模型与数据库
  12. CentOSv6.8 修改防火墙配置、修改SSH端口
  13. python基础8之自定义模块、if __name__==__main__:解释
  14. 【ASP.NET Core】如何隐藏响应头中的 “Kestrel”
  15. angularjs兼容thickbox 插件
  16. VS启动调试速度异常的缓慢问题
  17. 【HNOI 2018】道路
  18. Eclipse快捷键大全,导包快捷键:ctrl+Shift+/【转】
  19. POJ3279(KB1-D 熄灯问题)
  20. JavaScript匿名函数和回调函数

热门文章

  1. maven指定本地jar包
  2. 华南理工大学 “三七互娱杯” G HRY and tree
  3. Docker 容器(container)及资源限制
  4. Tomcat&amp;Servlet笔记
  5. 【SSL1786】麻将游戏
  6. PHP之简单工厂模式(二)
  7. 在SQL中存储过程的一般语法
  8. mysql proxysql的简单部署读写分离
  9. 封装class类--分割类名后
  10. 你不知道的props和state