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

最新文章

  1. Bagging与随机森林算法原理小结
  2. iOS 之 退出app(项目)的几种方法
  3. java 使用递归获取指定文件路径目录,删除指定的文件后缀(可扩展,根据具体需要的删除的后缀进行配置)~~
  4. 循环执行n次的代码
  5. NK3C程序配置
  6. ytu 1301:Excel地址转换(水题,进制转换)
  7. AIDL进程间调用与Binder的简单介绍
  8. nRF52系列——Get started
  9. MTK Android 默认值修改笔记
  10. Repository仓储 UnitofWork
  11. Scala 专题指南
  12. 类似智能购票的demo--进入页面后默认焦点在第一个输入框,输入内容、回车、right时焦点自动跳到下一个,当跳到select时,下拉选项自动弹出,并且可以按上下键选择,选择完成后再跳到下一个。
  13. Tomcat access log配置
  14. Linux 打开句柄限制的调整
  15. JVM总括:目录
  16. 【BZOJ4161】Shlw loves matrixI (常系数齐次线性递推)
  17. C++学习(十一)(C语言部分)之 练习
  18. HDFS操作及小文件合并
  19. iOS开发需要学习哪些内容?
  20. [翻译] TCBlobDownload

热门文章

  1. win10下CorelDRAW菜单栏字体变成白色了怎么办?
  2. hdu2614 Beat
  3. 使用CablleStatement调用存储过程
  4. Sona &amp;&amp; Little Elephant and Array &amp;&amp; Little Elephant and Array &amp;&amp; D-query &amp;&amp; Powerful array &amp;&amp; Fast Queries (莫队)
  5. 安装idea
  6. done
  7. SpringBoot2.0 监听器ApplicationListener的使用-监听ApplicationReadyEvent事件
  8. MyBatis学习总结(7)——Mybatis缓存
  9. windows部署iBase4J
  10. ASP.NET-POSTBACK是什么