首页 > 其他 > 详细

CareerCup Trie Prefix Tree

时间:2014-02-25 17:09:28      阅读:367      评论:0      收藏:0      [点我收藏+]
Return a shortest prefix of <code>word</code> that is <em>not</em> a prefix of any word in the <code>list</code> 

e.g. 
word: cat, it has 4 prefixes: “”, “c”, “ca”, “cat” 
list: alpha, beta, cotton, delta, camera 

Result is “cat”

------------------------------------------------------------------------------

#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
const int sonnum=26,base=‘a‘;
class Trie
{
 public:
  int num;//to remember how many word can reach here,that is to say,prefix
  bool terminal;//If terminal==true ,the current point has no following point
  Trie *son[sonnum];//the following point
  Trie(bool terminal = true, int num = 0):terminal(terminal), num(num){
    for (int i = 0; i < sonnum; ++i)
      son[i] = NULL;
  }
};
Trie* BuildTrie()// create a new node
{
  Trie *root=new Trie(true, 0);
  root->terminal = false;
  return root;
}
void Insert(Trie* root, string& s)// insert a new word to Trie tree
{
  for(int i=0; i<s.length(); ++i)
  {
    if(root->son[s[i]-base] == NULL)
	    root->son[s[i]-base]=new Trie();
    else 
	    root->son[s[i]-base]->num++;
  	root->terminal = false;
	  root=root->son[s[i]-base];
  }
  root->terminal=true;
}
void Delete(Trie *root)// delete the whole tree
{
  if(root!=NULL)
  {
    for(int i=0;i<sonnum;++i)
	    if(root->son[i]!=NULL)
		    Delete(root->son[i]);
    delete root; 
    root=NULL;
  }
}
Trie* Find(Trie *root,string& s)//trie to find the current word
{
  for(int i=0;i<s.length();++i)
    if(root->son[s[i]-base]!=NULL)
      root=root->son[s[i]-base];
    else 
			return NULL;
  return root;
}
void ListAll(Trie *root,string& cur)
{
  if (root->terminal) {
    cout << cur;
    return;
	}
	else {
	  for (int i = 0; i < sonnum; ++i)
	    if (root->son[i]) {        
	      string tmp = "a";
        tmp[0] += i;
        string next = cur + tmp;
		    ListAll(root->son[i], next);		  
		  }
	}
}
 
int main() {
  Trie* trie = BuildTrie();
  string str[] = {"abc", "ab", "ade", "ace"};
  for (int i = 0; i < 4; ++i)
	  Insert(trie, str[i]);
  string s = "a";
  Trie *searchWord = Find(trie, s);
  ListAll(searchWord, s);		
	
  return 0;
}


CareerCup Trie Prefix Tree

原文:http://blog.csdn.net/taoqick/article/details/19841165

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!