hihoCoder#1014：Trie树

建立Trie树，输出前缀单词个数。

#include <iostream>
#include <vector>
using namespace std;

struct node {
    char value;
    int times;
    node* sons[26];
    node(char a) {
        value = a;
        times = 1;
        for(int i = 0; i < 26; i++)
            sons[i] = NULL;
    }
};

node* root;

void insert_words(string s) {
    node* now = root;
    for(int i = 0; i < s.size() ;i++) {
        node* t = now->sons[s[i] - 'a'];
        if(t != NULL) {
            t->times++;
            now = t;
        }
        else {
            t = new node(s[i]);
            now->sons[s[i] - 'a'] = t;
            now = t;
        }
    }
}

int query_times(string s) {
    node* now = root;
    for(int i = 0; i < s.size() ;i++) {
        node* t = now->sons[s[i] - 'a'];
        if(t != NULL) {
            now = t;
        }
        else
            return 0;
    }
    return now->times;
}

int main()
{
    int n, m;
    string inputstr;
    cin >> n;
    root = new node('0');

    for(int i = 0; i < n; i++) {
        cin >> inputstr;
        insert_words(inputstr);
    }

    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> inputstr;
        cout << query_times(inputstr) <<endl;
    }

    return 0;
}