AC自动机解题记录
2024-03-01 22:53:48
1.HDU 2222 Keywords Search
模板题
#include <bits/stdc++.h>
#define fir first
#define sec second
#define EPS 1e-12
using namespace std; typedef long long LL;
typedef pair<int , int > pii;
const int MAXN=5e5+; struct Trie{
int nxt[MAXN][],fail[MAXN],ed[MAXN];
int root,L;
int newnode(){
for(int i=;i<;i++)
nxt[L][i]=-;
ed[L++]=;
return L-;
}
void init(){
L=;
root=newnode();
}
void Insert(char buf[]){
int len=strlen(buf);
int now=root;
for(int i=;i<len;++i){
if(nxt[now][buf[i]-'a']==-)
nxt[now][buf[i]-'a']=newnode();
now=nxt[now][buf[i]-'a'];
}
ed[now]++;
}
void build(){
queue <int > Q;
fail[root]=root;
for(int i=;i<;++i)
if(nxt[root][i]==-)
nxt[root][i]=root;
else{
fail[nxt[root][i]]=root;
Q.push(nxt[root][i]);
}
while(!Q.empty()){
int now=Q.front();Q.pop();
for(int i=;i<;++i)
if(nxt[now][i]==-)
nxt[now][i]=nxt[fail[now]][i];
else{
fail[nxt[now][i]]=nxt[fail[now]][i];
Q.push(nxt[now][i]);
}
}
}
int query(char buf[]){
int len=strlen(buf);
int now=root;
int res=;
for(int i=;i<len;++i){
now=nxt[now][buf[i]-'a'];
int temp=now;
while(temp!=root){
res+=ed[temp];
ed[temp]=;
temp=fail[temp];
}
}
return res;
}
};
Trie ac;
char buf[];
int main()
{
int Test;
int N;
scanf("%d",&Test);
while(Test--){
scanf("%d",&N);
ac.init();
for(int i=;i<N;++i)
{
scanf("%s",buf);
ac.Insert(buf);
}
ac.build();
scanf("%s",buf);
printf("%d\n",ac.query(buf));
}
return ;
}
2.HDU 2896 病毒侵袭
给模式串分配id
#include <bits/stdc++.h>
#define fir first
#define sec second
#define EPS 1e-12
using namespace std; typedef long long LL;
typedef pair<int , int > pii;
const int MAXN=*+; struct Trie{
int nxt[MAXN][],fail[MAXN],ed[MAXN];
int root,L;
int newnode(){
for(int i=;i<;i++)
nxt[L][i]=-;
ed[L++]=-;
return L-;
}
void init(){
L=;
root=newnode();
}
void Insert(char buf[],int id){
int len=strlen(buf);
int now=root;
for(int i=;i<len;++i){
if(nxt[now][buf[i]-]==-)
nxt[now][buf[i]-]=newnode();
now=nxt[now][buf[i]-];
}
ed[now]=id;
}
void build(){
queue <int > Q;
fail[root]=root;
for(int i=;i<;++i)
if(nxt[root][i]==-)
nxt[root][i]=root;
else{
fail[nxt[root][i]]=root;
Q.push(nxt[root][i]);
}
while(!Q.empty()){
int now=Q.front();Q.pop();
for(int i=;i<;++i)
if(nxt[now][i]==-)
nxt[now][i]=nxt[fail[now]][i];
else{
fail[nxt[now][i]]=nxt[fail[now]][i];
Q.push(nxt[now][i]);
}
}
}
bool vis[];
bool query(char buf[],int id,int N){
int len=strlen(buf);
int now=root;
bool flag=false;
memset(vis,false,sizeof(vis));
for(int i=;i<len;++i){
now=nxt[now][buf[i]-];
int temp=now;
while(temp!=root){
if(ed[temp]!=-){
vis[ed[temp]]=true;
flag=true;
}
temp=fail[temp];
}
}
if(!flag) return false;
printf("web %d:",id);
for(int i=;i<=N;++i)
if(vis[i]) printf(" %d",i);
puts("");
return true;
}
};
Trie ac;
char buf[+];
int main()
{
int N,M;
scanf("%d",&N);
ac.init();
for(int i=;i<=N;++i)
{
scanf("%s",buf);
ac.Insert(buf,i);
}
ac.build();
scanf("%d",&M);
int tot=;
for(int i=;i<=M;++i){
scanf("%s",buf);
if(ac.query(buf,i,N)) tot++;
}
printf("total: %d\n",tot);
return ;
}
3.HDU 3065 病毒侵袭持续中
给模式串分配id 并记录出现次数
#include <bits/stdc++.h>
#define fir first
#define sec second
#define EPS 1e-12
using namespace std; typedef long long LL;
typedef pair<int , int > pii;
const int MAXN=*+; int res[+];
char virus[+][]; struct Trie{
int nxt[MAXN][],fail[MAXN],ed[MAXN],ed1[MAXN];//ed 存编号 ed1存个数
int root,L;
int newnode(){
for(int i=;i<;i++)
nxt[L][i]=-;
ed[L]=-;
ed1[L++]=;
return L-;
}
void init(){
L=;
root=newnode();
}
void Insert(char buf[],int id){
int len=strlen(buf);
int now=root;
for(int i=;i<len;++i){
if(nxt[now][buf[i]-]==-)
nxt[now][buf[i]-]=newnode();
now=nxt[now][buf[i]-];
}
ed[now]=id;
ed1[now]++;
}
void build(){
queue <int > Q;
fail[root]=root;
for(int i=;i<;++i)
if(nxt[root][i]==-)
nxt[root][i]=root;
else{
fail[nxt[root][i]]=root;
Q.push(nxt[root][i]);
}
while(!Q.empty()){
int now=Q.front();Q.pop();
for(int i=;i<;++i)
if(nxt[now][i]==-)
nxt[now][i]=nxt[fail[now]][i];
else{
fail[nxt[now][i]]=nxt[fail[now]][i];
Q.push(nxt[now][i]);
}
}
}
void query(char buf[],int N){
for(int i=;i<=N;++i) res[i]=;
int len=strlen(buf);
int now=root;
for(int i=;i<len;++i){
now=nxt[now][buf[i]-];
int temp=now;
while(temp!=root){
if(ed[temp]!=-){
res[ed[temp]]++;
}
temp=fail[temp];
}
}
for(int i=;i<=N;++i)
if(res[i]) printf("%s: %d\n",virus[i],res[i]);
}
};
Trie ac;
char buf[+];
int main()
{
int N;
while(~scanf("%d",&N)){
ac.init();
for(int i=;i<=N;++i)
{
scanf("%s",virus[i]);
ac.Insert(virus[i],i);
}
ac.build();
scanf("%s",buf); ac.query(buf,N);
}
return ;
}
4.Gym - 101741K Consistent Occurrences
离线AC自动机，把所有询问的模式串建立自动机用id标记不同的询问，然后查询时有点麻烦地从左到右记录出现的不相交子串，开个数组记答案，还要开个数组记位置。
最让人没想到的是还会出现相同的询问，所以要处理相同模式串的id，以免出现后出现的询问覆盖前出现。
#include <bits/stdc++.h>
#define fir first
#define sec second
#define EPS 1e-12
using namespace std; typedef long long LL;
typedef pair<int , int > pii;
const int MAXN=2e5+; int res[+];
int evelen[+];
int loc[+];
int strid[+]; struct Trie{
int nxt[MAXN][],fail[MAXN],ed[MAXN],ed1[MAXN];//ed 存编号 ed1存个数
int root,L;
int newnode(){
for(int i=;i<;i++)
nxt[L][i]=-;
ed[L]=-;
ed1[L++]=;
return L-;
}
void init(){
L=;
root=newnode();
}
void Insert(string buf,int id){
int len=buf.size();
int now=root;
for(int i=;i<len;++i){
if(nxt[now][buf[i]-'a']==-)
nxt[now][buf[i]-'a']=newnode();
now=nxt[now][buf[i]-'a'];
}
ed[now]=id;
ed1[now]++;
}
void build(){
queue <int > Q;
fail[root]=root;
for(int i=;i<;++i)
if(nxt[root][i]==-)
nxt[root][i]=root;
else{
fail[nxt[root][i]]=root;
Q.push(nxt[root][i]);
}
while(!Q.empty()){
int now=Q.front();Q.pop();
for(int i=;i<;++i)
if(nxt[now][i]==-)
nxt[now][i]=nxt[fail[now]][i];
else{
fail[nxt[now][i]]=nxt[fail[now]][i];
Q.push(nxt[now][i]);
}
}
}
void query(string buf,int N){
for(int i=;i<=N;++i) { res[i]=; loc[i]=-;}
int len=buf.size();
int now=root;
for(int i=;i<len;++i){
now=nxt[now][buf[i]-'a'];
int temp=now;
while(temp!=root){
if(ed[temp]!=-){
int _id=ed[temp];
if(i>=loc[_id]+evelen[_id]){
res[_id]++;
//printf("loc[%d] = %d\n",_id,loc[_id]);
loc[_id]=i;
//printf("%d: loc[%d] = %d\n",i,_id,loc[_id]);
}
}
temp=fail[temp];
}
}
for(int i=;i<=N;++i)
printf("%d\n",res[strid[i]]);
}
};
Trie ac;
string buf;
string ob;
map<string ,int > mp;
int main()
{
ios::sync_with_stdio(false);
int N,M;
cin>>N>>M;
cin>>ob;
ac.init();
for(int i=;i<=M;++i)
{
cin>>buf;
if(mp.count(buf)) strid[i]=mp[buf];
else{
mp[buf]=i;
strid[i]=i;
}
evelen[strid[i]]=buf.size();
ac.Insert(buf,strid[i]);
}
ac.build();
ac.query(ob,M);
return ;
}
最新文章
- 【腾讯Bugly干货分享】微信终端跨平台组件 mars 系列(二) - 信令传输超时设计
- POJ2942 Knights of the Round Table（点双连通分量 + 二分图染色）
- 深搜+回溯 POJ 2676 Sudoku
- c++ 类型安全
- 夺命雷公狗ThinkPHP项目之----企业网站30之网站前台头部导航的高亮显示
- /usr/include/gnu/stubs.h:7:27: error: gnu/stubs-32.h:No such file or directory的解决办法
- do break的妙用
- Android实例-如何将文件打包到安装文件(XE8+小米2)
- JS框架~Angularjs
- D - 金樽清酒斗十千(搜索dfs)
- hdu_2546_饭卡(01背包)
- 1583: [Usaco2009 Mar]Moon Mooing 哞哞叫
- Javascript之pixi框架学习
- 虚拟环境更新HA
- vs2017 重新生成报错 MSB4057 BuildDependsOn DependsOnTargets ContainerPrepareForLaunch 解决办法
- 开启mysql-binlog日志操作步骤
- AD 10使用技巧---新学习
- UML model refactoring: a systematic literature review
- 使用Three.js挖空安装门来解决重叠闪烁的问题
- Linux系统中文件定位与查找
热门文章
- #学习笔记#jsp
- glog学习（一）：glog的编译及demo
- CRM项目之stark组件
- 十八、springcloud(四)熔断器
- Nginx中文url出现404问题
- 汉语言处理工具pyhanlp的拼音转换与字符正则化
- springboot对oracle的配置
- can't access lexical declaration `a' before initialization
- SyntaxError: 'ascii' codec can't decode byte 0xe4 in position 7: ordinal not in range(128)
- docker上搭建consul集群全流程