NYOJ 1085 数单词（AC自动机模板题） - c++编程基础

数单词

时间限制：1000 ms | 内存限制：65535 KB 难度：4

描述

为了能够顺利通过英语四六级考试，现在大家每天早上都会早起读英语。 LYH本来以为自己在6月份的考试中可以通过六级，可是没想到，成绩出来以后，居然没有通过。所以他不得不付出更多的时间来学习英语。要想通过六级，最基本的要求就是词汇量。为了能够更快的记住一些陌生单词，LYH有时会找一些英语文章来读。今天早上，LYH又找了一篇文章。读之前，他突然萌生出一个想法：文章中哪些单词出现的次数最多呢？

输入

第一行输入一个整数T，表示有T组测试数据（1≤T≤200）。
对于每组测试数据，第一行输入一个整数n（1≤n≤150），表示LYH要查询的单词数量（有些单词可能会重复出现）。
接下来n行，每行输入一个单词，长度不大于100。
最后一行包含一个由小写字母组成的英语文章（字符串），长度不大于10^6。

输出

对于每组数据，第一行输出一个整数，表示单词出现的次数。
然后按照输入顺序，每行输出一个出现次数最多的单词。如果有重复出现的单词，把它们全部输出。

样例输入

2
3
good
oo
one
goodafternooneveryone
1
to
welcometotopcoder

样例输出

2
oo
one
2
to

分析：这就是一个AC自动机模板题，要注意的是查询的单词中，一个单词可能会出现多次，这里要处理一下。

#include 
      
       
#include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             using namespace std; #define SIGMA_SIZE 26 //文本串字符内容 #define MAXNODE 20000 //节点数量 #define TEXT_SIZE 1000005 //文本串长度 #define P_SIZE 100 //模式串长度 #define P_NUM 200 //模式串数量 map 
            
              mp; struct AhoCorasickAutomata { int cnt[P_NUM]; int sz; int ch[MAXNODE][SIGMA_SIZE]; int f[MAXNODE]; int val[MAXNODE]; int last[MAXNODE]; void Init() { sz = 1; memset(ch[0],0,sizeof(ch[0])); memset(cnt,0,sizeof(cnt)); mp.clear(); } int idx(char c) { return c - 'a'; } void Insert(char *s,int v) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++) { int c = idx(s[i]); if(!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = v; mp[string(s)] = v; } void print(int j) { if(j) { cnt[val[j]]++; print(last[j]); } } void Find(char *T) { int n = strlen(T); int j = 0; for(int i = 0; i < n; i++) { int c = idx(T[i]); while(j && !ch[j][c]) j = f[j]; j = ch[j][c]; if(val[j]) print(j); else if(last[j]) print(last[j]); } } void Get_Fail() { queue
             
               q; f[0] = 0; for(int c = 0; c
              
                Max_cnt) Max_cnt = ac.cnt[i]; printf("%d\n", Max_cnt); for(int i = 1; i <= n; i++) if(ac.cnt[mp[string(P[i])]] == Max_cnt) printf("%s\n", P[i]); } return 0; }