【AC自动机】Lougu P3796-白红宇

【AC自动机】Lougu P3796

阅读量：4966 次

发布时间：2019-06-12

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

题目描述

有

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数 $\leq N \leq 1501≤N≤150。$

接下去 $NNN行，每行一个长度小于等于707070的模式串。下一行是一个长度小于等于10610^6106的文本串TTT。$

输入结束标志为

输出格式：

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

输入输出样例

输入样例#1：

2abababababababac6betaalphahahadeltadedetatadedeltalphahahahototatalpha0

输出样例#1：

4aba2alphahaha

题解

写个AC自动机的板子上来。。。

反正就是先建一棵trie树，然后bfs找失配指针（类似KMP）。。。

然后再在上面搞些奇奇怪怪的东西。。。

代码

//by 减维#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #define ll long long#define maxn 1000005using namespace std;struct trie{ int end,fail,to[26]; void cle(){ memset(to,0,sizeof(to)); end=fail=0; }}ac[maxn];struct anss{ int pos,num;}ans[maxn];int n,tot;string s[155];bool cmp(const anss&x,const anss&y){ if(x.num==y.num)return x.pos
               
                y.num;}void build(int x){ int now=0,ch; int len=s[x].length(); for(int i=0;i

q; for(int i=0;i<26;++i) if(ac[0].to[i])q.push(ac[0].to[i]),ac[ac[0].to[i]].fail=0; while(!q.empty()) { int d=q.front(); q.pop(); for(int i=0;i<26;++i) { int dd=ac[d].to[i]; if(dd)ac[dd].fail=ac[ac[d].fail].to[i],q.push(dd); else ac[d].to[i]=ac[ac[d].fail].to[i]; } }}void ask(){ int now=0,ch; int len=s[0].length(); for(int i=0;i

>s[i]; build(i); ans[i].pos=i; ans[i].num=0; } getf(); cin>>s[0]; ask(); }}

转载于:https://www.cnblogs.com/rir1715/p/8006600.html

你可能感兴趣的文章