当前位置: 首页 > news >正文

AC自动机

模板:洛谷P5357

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fail[N],tr[N][26],idx,n,times[N];
//end[i]表示第i个字符的结尾编号
int ed[N];
vector<int> edges[N];
void insert(int i,string &s){int cur=0;for(char &ch:s){int path=ch-'a';if(!tr[cur][path])tr[cur][path]=++idx;cur=tr[cur][path];}ed[i]=cur;
}void dfs(int u){for(int &v:edges[u]){dfs(v);times[u]+=times[v];}
}void init(){queue<int> q;for(int i=0;i<26;i++){if(tr[0][i]){q.push(tr[0][i]);}}while(q.size()){int u=q.front();q.pop();for(int i=0;i<26;i++){//存在更新fail,不存在更新直通表if(tr[u][i]){fail[tr[u][i]]=tr[fail[u]][i];q.push(tr[u][i]);}else{tr[u][i]=tr[fail[u]][i];}}}
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){string t;cin>>t;insert(i,t);}string s;cin>>s;//初始化直通表和fail数组init();int m=s.size();for(int cur=0,i=0;i<m;i++){cur=tr[cur][s[i]-'a'];//增加匹配次数times[cur]++;}//建反图for(int i=1;i<=idx;i++){edges[fail[i]].push_back(i);}//遍历fail指针建的树//汇总每个节点的词频dfs(0);for(int i=1;i<=n;i++){cout<<times[ed[i]]<<endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=16301

相关文章:

  • 虚拟机开机网络连接失败
  • unprofitable25,3
  • 随机过程学习笔记
  • Easysearch 国产替代 Elasticsearch:8 大核心问题解读
  • 9.24 闲话
  • AGC023F 题解
  • 个人介绍
  • C#学习2
  • AGC203F 题解
  • 高级的 SQL 查询技巧
  • 25,9.24日报
  • 在台风天找回了生活的本貌
  • 第二周第三天2.3
  • 欧几里得算法
  • Error response from daemon: could not select device driver nvidia with capabilities: [[gpu]]
  • 全内存12306抢票系统设计:基于位运算的高效席位状态管理
  • 第三天
  • adobe illustrator中如何打出度数的上标
  • day003
  • newDay03
  • 9.24总结
  • 常用API
  • 9月24日
  • 2025.9.24总结 - A
  • RAG 检索优化的五种常见手段及实现
  • 课程学习
  • 代码规范与数学之美
  • Day3
  • vant