编程学习笔记 1: TRIE

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);

}

}