HihoCoder——Trie树

本文出自：http://blog.****.net/svitter

原题：http://hihocoder.com/contest/hiho2/problem/1

题解：使用Trie树。。基础题目。一開始使用memset(child, 0, sizeof(child))总是MLE，应该是NULL定义的问题。指针直接为0是不合适的。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

string str;

struct TrieNode
{
    TrieNode *child[26];
    //
    int num;
    TrieNode()
    {
        num = 0;
        memset(child, NULL, sizeof(child));
    }
};

TrieNode *root;
int temp;

void Build(string s)
{
    TrieNode *p = root;
    for(int i = 0; i < s.length(); i++)
    {
        temp = s[i]-'a';
//      cout << temp << endl;
        if(p->child[temp] == NULL)
        {
            p->child[temp] = new TrieNode;
        }
        p = p->child[temp];
        p->num ++;
    }
}

int check(string s)
{
    TrieNode *p = root;
    for(int i = 0; i < s.length(); i++)
    {
        temp = s[i]-'a';
        if(p->child[temp] == NULL)
            return 0;
        p = p->child[temp];
    }
    return p->num;
}

int main()
{
    int n, m;
    scanf("%d", &n);
    root = new TrieNode;
    while(n--)
    {
        cin >> str;
        Build(str);
    }

    scanf("%d", &m);
    while(m--)
    {
        cin >> str;
        cout << check(str) << endl;
    }

    return 0;
}