/** 
 * 字典树的Java实现。实现了插入、查询以及深度优先遍
 * Trie tree's java implementation.(Insert,Search,DFS) 
 * @author RXJ 
 * 
 */ 
public class Trie {
	final int Max_size=26;
	public class TrieNode{
		int nCount;// 记录该字符出现次�?
		char ch; //记录该字�?
		TrieNode[] child;
		public TrieNode(){
			nCount=1;
			child = new TrieNode[Max_size];
		}
	}
	//字典树的插入与构�?
	public void createTrie(TrieNode node ,String str){
		if(str==null || str.length()==0){
			return ;
		}
		char[] leters=str.toCharArray();	//单词转换为一个个字符
		for(int i=0 ;i<leters.length;i++){
			int pos=leters[i]-'a';
			if(node.child[pos]==null){
				node.child[pos]= new TrieNode(); //如果对应的位置的字母为null
			}else{
				node.child[pos].nCount++; //这个节点字符�?1
			}
			node.ch=leters[i];
			node=node.child[pos]; //重置node为下�?��的node 从�?实现下一个字符的添加
		}
	}
	//字典树的查找
	public int findCount(TrieNode node,String str){
		if(str==null || str.length()==0){
			return -1;
		}
		char[] leters=str.toCharArray();
		for(int i=0 ;i<leters.length;i++){
			int pos = leters[i]-'a';
			if(node.child[pos]==null){
				return 0;
			}else{
				node=node.child[pos]; //到下�?��节点再查�?
			}
		}
		return node.nCount;
	}
	public static void main(String arg[]){
		 String[] strs={ 
	 "banana", 
	 "band", 
	 "bee", 
	 "absolute", 
	 "acm", 
	 }; 
	 String[] prefix={ 
	 "ba", 
	 "b", 
	 "band", 
	 "abc", 
	 }; 
	 Trie tree = new Trie(); 
	 TrieNode root=tree.new TrieNode(); 
	 
	 for (String s : strs) { 
	 tree.createTrie(root, s); 
	 }
	 for(String pre:prefix){ 
	 int num=tree.findCount(root,pre); 
	 System.out.println(pre+" "+num); 
	 } 
	}
	
}