程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ 1085 數單詞 (AC自動機模板題)

NYOJ 1085 數單詞 (AC自動機模板題)

編輯:C++入門知識

NYOJ 1085 數單詞 (AC自動機模板題)


數單詞

時間限制: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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved