问题:http://hihocoder.com/problemset/problem/1014
给定一个字符串字典dict,输入字符串str, 要求从dict中找出所有以str为前缀的字符串个数。
构建Trie树:
1) 一个节点有多个子节点。用vector<Node*> nexts 存储。
2) 两个字符串的相同前缀部分共用同一条路径。
3) 每个节点包含计数变量 cnt, 表示有多少个字符串共用该节点
复杂度分析:
假定dict中的字符串个数 n, 字符串的长度 l
1)建树:O(n^2*l)
2) 查找:O(n*l)
源码:
#include <iostream>
#include <vector>
#include <string>
using namespace std; //node structure in Trie tree
struct Node
{
Node(char _chr = -){chr = _chr; cnt = ;}
char chr;
vector<Node*> nexts;
int cnt;//how many strings pass current node
}; int main()
{
Node* root = new Node;//root of dictornary
Node* current;
vector<Node*> v_current;
int cnt, vsize, i, j, strLen;
string str; //create Trie tree
cin>>cnt;
while(cnt-- > )
{
cin>>str;
strLen = str.length();
current = root;
for(i = ; i < strLen; i++)
{
v_current = current->nexts;
vsize = v_current.size();
//try to find str[i] in current tree
for(j = ; j < vsize; j++)
{
if(v_current[j]->chr == str[i])
break;
}
if(j == vsize)//not found, create a new node
{
Node* tmp = new Node(str[i]);
current->nexts.push_back(tmp);
}
current = current->nexts[j];
current->cnt++;//increase count of current node
}
} cin>>cnt;
while(cnt-- > )
{
cin>>str;
strLen = str.length();
current = root;
for(i = ; i < strLen; i++)
{
v_current = current->nexts;
vsize = v_current.size();
for(j = ; j < vsize; j++)
if(v_current[j]->chr == str[i])
break;
if(j == vsize)//not found
{
cout<<''<<endl;
break;
}
current = v_current[j];
}
if(i == strLen)
cout<<current->cnt<<endl;
}
return ;
}