首页 > > 程序设计 > C/C++ >

P3796 【模板】AC自动机（加强版）

2018-06-17 22:16:05来源：未知阅读 ()

题目描述

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

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数，表示共有个模式串， $1 \leq N \leq 150$ 。

接下去行，每行一个长度小于等于的模式串。下一行是一个长度小于等于的文本串。

输入结束标志为。

输出格式：

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

输入输出样例

输入样例#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 }