數單詞
時間限制: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
- 例子輸出
-
分析:這就是一個AC自己主動機模闆題,要注意的是查詢的單詞中,一個單詞可能會出現多次。這裡要處理一下。2 oo one 2 to
#include <cstring> #include <cstdio> #include <algorithm> #include <map> #include <string> #include <queue> using namespace std; #define SIGMA_SIZE 26 //文本串字元内容 #define MAXNODE 20000 //節點數量 #define TEXT_SIZE 1000005 //文本串長度 #define P_SIZE 100 //模式串長度 #define P_NUM 200 //模式串數量 map <string, int> 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<int> q; f[0] = 0; for(int c = 0; c<SIGMA_SIZE; c++) { int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); last[u] = 0; } } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c<SIGMA_SIZE; c++) { int u = ch[r][c]; if(!u) continue; q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]] ? f[u] : last[f[u]]; } } } }; char text[TEXT_SIZE]; char P[P_NUM][P_SIZE]; AhoCorasickAutomata ac; int n, T; int main() { scanf("%d", &T); int cas = 0; while(T--) { scanf("%d", &n); ac.Init(); for(int i = 1; i <= n; i++) { scanf("%s", P[i]); ac.Insert(P[i], i); } ac.Get_Fail(); scanf("%s", text); ac.Find(text); int Max_cnt = -1; for(int i = 1; i <= n; i++) if(ac.cnt[i] > Max_cnt) Max_cnt = ac.cnt[i]; printf("%d ", Max_cnt); for(int i = 1; i <= n; i++) if(ac.cnt[mp[string(P[i])]] == Max_cnt) printf("%s ", P[i]); } return 0; }