博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AC自动机板子(from. qwer)
阅读量:4589 次
发布时间:2019-06-09

本文共 1437 字,大约阅读时间需要 4 分钟。

#include 
#include
#include
#include
#include
#include
#include
using namespace std;const int N=510000;struct Tri{ int Next[N][26], fail[N], val[N], root, L; void init() {L = 0;root = newnode();} int newnode() { for(int i = 0;i < 26;i++) Next[L][i] = -1; val[L++] = 0; return L - 1; } void insert(char s[]) { int len = strlen(s), cur = root; for(int i = 0;i < len;i++) { if(Next[cur][s[i]-'a'] == -1) Next[cur][s[i]-'a'] = newnode(); cur = Next[cur][s[i]-'a']; } val[cur]++; } void build() { queue
Q; fail[root] = root; for(int i = 0;i < 26;i++) if(Next[root][i] == -1) Next[root][i] = root; else { fail[Next[root][i]] = root; Q.push(Next[root][i]); } while(!Q.empty()) { int cur = Q.front(); Q.pop(); for(int i = 0;i < 26;i++) if(Next[cur][i] == -1) Next[cur][i] = Next[fail[cur]][i]; else { fail[Next[cur][i]]=Next[fail[cur]][i]; Q.push(Next[cur][i]); } } } int query(char s[]) { int len = strlen(s), cur = root, res = 0; for(int i = 0;i < len;i++) { cur = Next[cur][s[i]-'a']; int tmp = cur; while (tmp != root) { res += val[tmp]; val[tmp] = 0; tmp = fail[tmp]; } } return res; }};char s[N];Tri AC;int n;int main(){ scanf("%d",&n); AC.init(); for(int i = 0;i < n;i++) { scanf("%s",s); AC.insert(s); } AC.build(); scanf("%s",s); printf("%d\n",AC.query(s)); return 0;}

 

转载于:https://www.cnblogs.com/thmyl/p/6349743.html

你可能感兴趣的文章
嵌套循环及例题
查看>>
c++ 使用WinHTTP实现文件下载功能
查看>>
一个分发复制+mirror的bug
查看>>
LeetCode 520 Detect Capital
查看>>
完全教程 Aircrack-ng破解WEP、WPA-PSK加密利器[zz]
查看>>
什么是C#
查看>>
从云计算到容器到容器云
查看>>
shell 分支/循环
查看>>
api服务端接口安全
查看>>
python中的time模块
查看>>
MyBatis-Plus的简单使用
查看>>
C++学习笔记-标准库类型-Vector类型
查看>>
Oracle 树操作(select…start with…connect by…prior)
查看>>
python中的operator.itemgetter函数
查看>>
h5新特性--- 多媒体元素
查看>>
jQuery实现发送短信验证码后60秒倒计时
查看>>
【CSS】盒模型+选择器(你选择的要操作的对象)
查看>>
EM算法总结
查看>>
centos7开启防火墙和指定端口
查看>>
Android系统对话框——自己定义关闭
查看>>