HiHo一下 Week4 Trie图

HiHo

输入

每个输入文件有且仅有一组测试数据。

每个测试数据的第一行为一个整数N，表示河蟹词典的大小。

接下来的N行，每一行为一个由小写英文字母组成的河蟹词语。

接下来的一行，为一篇长度不超过M，由小写英文字母组成的文章。

对于60%的数据，所有河蟹词语的长度总和小于10, M<=10

对于80%的数据，所有河蟹词语的长度总和小于10^3, M<=10^3

对于100%的数据，所有河蟹词语的长度总和小于10^6, M<=10^6, N<=1000

输出

对于每组测试数据，输出一行"YES"或者"NO"，表示文章中是否含有河蟹词语。

样例输入

6
aaabc
aaac
abcc
ac
bcd
cd
aaaaaaaaaaabaaadaaac

样例输出

YES

思路

代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAX 26
struct Trie{
    int cnt;
    Trie *fail;
    Trie *next[MAX];
    Trie(){
        cnt = 0;
        for(int i=0;i<MAX;i++) next[i] = NULL;
    }
}; 
//build Trie Tree
void build(Trie *root,char *c){
    Trie *p=root;
    int pos;
    while(*c){
        pos = *c - 'a';
        if(p->next[pos]==NULL) p->next[pos]= new Trie();
        p = p->next[pos];
        c++;
    }
    p->cnt++;
}
//Swith Trie Tree to Trie Graph
void TrieG(Trie *root){
    queue <Trie *>q;
    root->fail=root;
    for(int i=0;i<MAX;i++){
        if(root->next[i]==NULL) root->next[i] = root;
        else{
            root->next[i]->fail = root;
            q.push(root->next[i]);
        }
    }
    while(!q.empty()){
        Trie *temp =q.front();
        q.pop();
        if((temp->fail->cnt >0)&&(temp->cnt==0))temp->cnt++; 
        for(int i=0;i<MAX;i++){
            if(temp->next[i]==NULL) temp->next[i] = temp->fail;
            else{
                temp->next[i]->fail = temp->fail->next[i];
                q.push(temp->next[i]);
            }
        }
    }
}
int main()
{   int n;
    bool flag = false;
    char words[1000000];
    Trie *root = new Trie();
    cin >> n;
    while(n--){
        cin>> words;
        build(root,words);
    }
    TrieG(root);
    char *s;
    cin >> words;
    s = words -1;
    Trie *temp = root;
    while(*++s){        
        temp = temp->next[*s - 'a'];
        if(temp->cnt>0){
            flag = true;
            break;
        }
    }
    string out = flag ? "YES":"NO";
    cout << out;
    return 0;
}