专栏首页数据结构与算法P3796 【模板】AC自动机(加强版)

P3796 【模板】AC自动机(加强版)

题目描述

有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。

输入输出格式

输入格式:输入含多组数据。

每组数据的第一行为一个正整数N,表示共有N个模式串,1<=N<=150

接下去N行,每行一个长度小于等于70的模式串。下一行是一个长度小于等于10^6 的文本串T。

输入结束标志为N=0。

输出格式:

对于每组数据,第一行输出模式串最多出现的次数,接下去若干行每行输出一个出现次数最多的模式串,按输入顺序排列。

输入输出样例

输入样例#1:

2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

输出样例#1:

4
aba
2
alpha
haha

就是个纯模板,没啥好说的,。

不过AC自动机真的是,,恶心到爆,,,

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #include<map>
  8 using namespace std;
  9 const int MAXN=100001;
 10 void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 char s[MAXN][101];
 18 char text[1000001];
 19 struct AC_Automata
 20 {
 21     int sz;
 22     int ch[MAXN][28];//trie树 
 23     int cnt[MAXN];// 每个单词出现的次数
 24     int val[MAXN];// 记录是否有单词
 25     int last[MAXN];
 26     int f[MAXN]; 
 27     int sigma_sz;
 28     map<string,int>mp;//出现的位置
 29     void Init()
 30     {
 31         memset(ch[0],0,sizeof(ch[0]));
 32         memset(cnt,0,sizeof(cnt));
 33         mp.clear();
 34         sz=1;    
 35         sigma_sz=26;
 36     }
 37     int idx(char c)
 38     {
 39         return c-'a';
 40     }
 41     void Insert(char *s,int pos)
 42     {
 43         int l=strlen(s); int now=0;
 44         for(int i=0;i<l;i++)
 45         {
 46             int c=idx(s[i]);
 47             if(!ch[now][c])
 48             {
 49                 memset(ch[sz],0,sizeof(ch[sz]));
 50                 val[sz]=0;
 51                 ch[now][c]=sz++;
 52             }
 53             now=ch[now][c];
 54         }
 55         val[now]=pos;//一个单词的结束
 56         mp[string(s)]=pos; // 记录这个字符串出现的位置,按顺序输出 
 57     }
 58     void getfail()
 59     {
 60         f[0]=0;
 61         queue<int>q;
 62         for(int i=0;i<sigma_sz;i++)
 63         {
 64             int u=ch[0][i];
 65             if(u)// 此处有单词出现
 66             {    
 67                 f[u]=0;// 连向根节点
 68                 q.push(u);
 69                 last[u]=0;// 上一个出现的单词一定是根节点    
 70                 // 上面两条语句没什么卵用,只是为了帮助理解AC自动机的含义 
 71             }
 72         }
 73         while(!q.empty())
 74         {
 75             int p=q.front();q.pop();
 76             for(int i=0;i<sigma_sz;i++)
 77             {
 78                 int u=ch[p][i];
 79                 if(!u)//没有孩子
 80                 {
 81                     ch[p][i]=ch[f[p]][i];// 补上一条不存在的边,减少查找次数 
 82                     continue;    
 83                 }
 84                 q.push(u);
 85                 int v=f[p];// 找到它的失陪指针
 86                 f[u]=ch[v][i];//因为我们在上面补上了一条不存在边,所以他一定存在孩子 
 87                 last[u]=val[f[u]] ? f[u] : last[f[u]];
 88                 //判断下是不是单词结尾  是, 不是
 89             }     
 90         }
 91     }
 92     int ok(int pos)
 93     {
 94         if(pos)
 95         {
 96             cnt[val[pos]]++;
 97             ok(last[pos]);
 98         }
 99     }
100     void find(char *s)// 查找模式串 
101     {
102         int l=strlen(s);
103         int j=0;// 当前节点的编号
104         for(int i=0;i<l;i++)
105         {
106             int c=idx(s[i]);
107             while(j&&!ch[j][c])    
108             j=f[j];// 顺着失配边走
109             j=ch[j][c]; // 取到儿子
110             if(val[j])    
111             ok(j);// 找到一个单词
112             else if(last[j])    
113             ok(last[j]);// 当前节点不行就看看上一个单词出现的位置行不行 
114         } 
115     }
116 }ac;
117 int n;
118 int main()
119 {
120     while(scanf("%d",&n)==1&&n!=0)
121     {
122         ac.Init();
123         for(int i=1;i<=n;i++)
124         {
125             scanf("%s",s[i]);
126             ac.Insert(s[i],i);
127         }
128         ac.getfail();
129         scanf("%s",text);
130         ac.find(text);
131         int ans=-1;
132         for(int i=1;i<=n;i++)
133             if(ac.cnt[i]>ans) ans=ac.cnt[i];
134         printf("%d\n",ans);
135         for(int i=1;i<=n;i++)
136             if(ac.cnt[i]==ans)
137                 printf("%s\n",s[i]);
138     }
139     return 0;
140 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 云识别-在一切看脸的时代,如何高效的打造人脸识别服务?

    摘要 如何利用机器学习高效地打造人脸识别服务? ? 人工智能与深度学习 早在几十年前,美国就已诞生了人工智能技术,而机器学习是实现人工智能的其中一种方法。机器学...

    IT大咖说
  • 机器学习在开心词场(自适应学习)中应用

    摘要 教育是最传统和复杂的社会活动,如何使用AI(机器学习)技术改造和促进人类自身学习(提高学习效率和学习效果) ,是互联网教育大数据及挖掘的基本问题;简单介绍...

    IT大咖说
  • 22:神奇的幻方

    22:神奇的幻方 总时间限制: 1000ms 内存限制: 65535kB描述 幻方是一个很神奇的N*N矩阵,它的每行、每列与对角线,加起来的数字和都是相同的。...

    attack
  • 成为一名数据分析师,应该掌握怎样的技术栈?

    数据分析师是不易被人工智能取代的新兴职业,相比算法工程师、人工智能工程师而言比较好入门。学好数据分析,也可为进一步的数据科学、机器学习打下一定的基础。 最近我知...

    爱吃西瓜的番茄酱
  • Mysql 集群高可用方案 MHA

    MHA是什么? MHA(master high availability) 是用来保证 Mysql 集群高可用性的,对 master 进行监控,发现 maste...

    dys
  • asd

    #include<iostream> #include<cstdio> #include<queue> using namespace std; priorit...

    attack
  • 萨达是否

    #include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include...

    attack
  • Python爬虫入门二之爬虫基础了解

    1.什么是爬虫 爬虫,即网络爬虫,大家可以理解为在网络上爬行的一直蜘蛛,互联网就比作一张大网,而爬虫便是在这张网上爬来爬去的蜘蛛咯,如果它遇到资源,那么它就会抓...

    zhisheng
  • #每日一题#4

    4、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是() A、head(tail(LS)) B、tail(...

    zhisheng
  • 02:同行列对角线的格子

    02:同行列对角线的格子 总时间限制: 1000ms 内存限制: 65536kB描述 输入三个自然数N,i,j (1<=i<=N,1<=j<=N),输出在一个...

    attack

扫码关注云+社区

领取腾讯云代金券