编程学习笔记 1: TRIE
上一篇 /
下一篇 2012-03-31 12:54:10
/ 个人分类:编程与算法
题目: http://poj.org/problem?id=2001
importjava.io.*;
importjava.util.*;
publicclassMain
{
publicstaticvoidmain(String[] args)
{
newMain().run();
}
PrintWriterout=null;
Noderoot=newNode();
voidrun()
{
Scanner in =newScanner(System.in);
out=newPrintWriter(System.out);
ArrayList<String> al =newArrayList<String>();
while(in.hasNext())
{
String word = in.next();
if(word.equals("@"))
break;
root.insert(word, 0);
al.add(word);
}
for(String w : al)
out.println(w +" "+root.prefix(w, 0));
out.close();
}
}
classNode
{
intcount= 0;
Node[]children=newNode[26];
voidinsert(String word,intstart)
{
count++;
if(start == word.length())
return;
if(children[word.charAt(start) -'a'] ==null)
children[word.charAt(start) -'a'] =newNode();
children[word.charAt(start) -'a'].insert(word, start + 1);
}
String prefix(String word,intstart)
{
if(start == word.length())
returnword;
if(count== 1)
returnword.substring(0, start);
returnchildren[word.charAt(start) -'a'].prefix(word, start + 1);
}
}
收藏
举报
TAG: