AC自动机笔记
2024-08-26 23:26:35
AC自动机
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define MAX 100001
#define u(n) (n-'a')
using namespace std;
struct ac{
int son[],fail,sum;
void init(){
memset(son,,sizeof(son));
sum=;
}
}a[];
queue<int>q;
int last[],ans=,n,tot=,len;
char st[],sp[][];
void init(){
for(char i='a';i<='z';i++){
if(a[].son[u(i)]){
q.push(a[].son[u(i)]);
a[a[].son[u(i)]].fail=;
}
}
while(!q.empty()){
for(char i='a';i<='z';i++){
if(a[q.front()].son[u(i)]){
q.push(a[q.front()].son[u(i)]);
int now=a[q.front()].fail;
while(now&&!a[now].son[u(i)]) now=a[now].fail;
if(a[now].son[u(i)]) a[q.back()].fail=a[now].son[u(i)];
else a[q.back()].fail=;
if(a[a[q.back()].fail].sum){
last[q.back()]=a[q.back()].fail;
}else{
last[q.back()]=last[a[q.back()].fail];
}
}
}
q.pop();
}
}
void ins(char st[]){
int s=;
for(int i=;i<strlen(st);i++){
if(a[s].son[u(st[i])]==){
a[s].son[u(st[i])]=++tot;
a[tot].init();
s=tot;
}else{
s=a[s].son[u(st[i])];
}
}
a[s].sum++;
}
void inc(int now){
if(a[now].sum){
ans+=a[now].sum;
a[now].sum=;
}
while(last[now]){
ans+=a[last[now]].sum;
a[last[now]].sum=;
now=last[now];
}
}
void solution(int len){
int now=;
for(int i=;i<=len;i++){
if(a[now].son[u(st[i])]){
now=a[now].son[u(st[i])];
}else{
while(now&&!a[now].son[u(st[i])]) now=a[now].fail;
if(a[now].son[u(st[i])]) now=a[now].son[u(st[i])];
}
inc(now);
}
}
int main(){
scanf("%d",&n);
a[].init();
a[].fail=;
for(int i=;i<=n;i++){
scanf("%s",sp[i]);
ins(sp[i]);
}
scanf("%s",st);
len=strlen(st);
init();
solution(len);
printf("%d",ans);
return ;
}
最新文章
- Bagging与随机森林算法原理小结
- iOS 之 退出app(项目)的几种方法
- java 使用递归获取指定文件路径目录,删除指定的文件后缀(可扩展,根据具体需要的删除的后缀进行配置)~~
- 循环执行n次的代码
- NK3C程序配置
- ytu 1301:Excel地址转换(水题,进制转换)
- AIDL进程间调用与Binder的简单介绍
- nRF52系列——Get started
- MTK Android 默认值修改笔记
- Repository仓储 UnitofWork
- Scala 专题指南
- 类似智能购票的demo--进入页面后默认焦点在第一个输入框,输入内容、回车、right时焦点自动跳到下一个,当跳到select时,下拉选项自动弹出,并且可以按上下键选择,选择完成后再跳到下一个。
- Tomcat access log配置
- Linux 打开句柄限制的调整
- JVM总括:目录
- 【BZOJ4161】Shlw loves matrixI (常系数齐次线性递推)
- C++学习(十一)(C语言部分)之 练习
- HDFS操作及小文件合并
- iOS开发需要学习哪些内容?
- [翻译] TCBlobDownload
热门文章
- win10下CorelDRAW菜单栏字体变成白色了怎么办?
- hdu2614 Beat
- 使用CablleStatement调用存储过程
- Sona &;&; Little Elephant and Array &;&; Little Elephant and Array &;&; D-query &;&; Powerful array &;&; Fast Queries (莫队)
- 安装idea
- done
- SpringBoot2.0 监听器ApplicationListener的使用-监听ApplicationReadyEvent事件
- MyBatis学习总结(7)——Mybatis缓存
- windows部署iBase4J
- ASP.NET-POSTBACK是什么