题目地址:http://hihocoder.com/problemset/problem/1014
不得不吐槽一下这个OJ,题目质量是很好的,但是提交代码后返回的信息也太少了吧!!!本机测试无误,提交后各种TLE。
#include <iostream>
#include <string>
#include <vector>
using namespace std;#define TREE_WIDTH 256
#define WORDLENMAX 10class TrieNode {
public:
char val;
int count;
TrieNode *next[TREE_WIDTH];
TrieNode(char val, int count) {
this->val = val;
this->count = count;
for (size_t i = 0; i < TREE_WIDTH; i++)
{
this->next[i] = NULL;
}
}
~ TrieNode() {
for (size_t i = 0; i < TREE_WIDTH; i++)
{
if (this->next[i] != NULL) {
delete this->next[i];
}
}
}
};int *insert(TrieNode *root, string &word) {
TrieNode *curr;
curr = root;
for (size_t i = 0; i< word.length(); ++i) {
if (curr->next[word[i]] == NULL) {
curr->next[word[i]] = new TrieNode(word[i], 0);
}
curr = curr->next[word[i]];
curr->count++;
}return 0;
}int serachTrie(TrieNode *root, string &word) {
TrieNode *curr = root;for (size_t i = 0; curr && i<word.length(); ++i) {
curr = curr->next[word[i]];
}if (!curr)
return 0;
else
return curr->count;
}int main() {
vector<string> vstr1, vstr2;
int n;TrieNode root(0, 0);cin >> n;
for (size_t i = 0; i < n; ++i) {
string str;
cin >> str;
vstr1.push_back(str);
}int m;
cin >> m;
for (size_t i = 0; i<m; ++i) {
string str;
cin >> str;
vstr2.push_back(str);}for (size_t i = 0; i < n; i++)
{
insert(&root, vstr1[i]);
}for (size_t i = 0; i < m; i++)
{
cout << serachTrie(&root, vstr2[i]) << endl;
}return 0;
}