/**
* Trie - a tree for keeping a set of words, factoring out duplicate prefixes.
* Demo application - keep a sorted set of words.
*
* INPUT: a list of words.
* OUTPUT: the same list, sorted and without duplicates.
*
* Author: Erel Segal
* Created: 2010-10-14
*/
#include <map>
#include <string>
#include <iostream>
using namespace std;
class Trie;
typedef Trie* PTrieNode;
class Trie {
map< char ,PTrieNode> myChildren;
bool isWordEnd; // "true" if a word ends in this node
public :
Trie( ) : isWordEnd( false ) { }
/* recursively add a single word to the node */
void add ( const char * newWord) {
char first = newWord[ 0 ] ;
if ( ! first) { // empty word
isWordEnd = true ;
} else {
if ( ! myChildren[ first] ) {
myChildren[ first] = new Trie( ) ;
}
myChildren[ first] - > add( newWord+ 1 ) ;
}
}
/* recursively print all words in the node in order */
void print ( ostream& out, string prefix) const {
if ( isWordEnd) {
out << prefix << " " ;
}
map< char ,PTrieNode> :: const_iterator it;
for ( it= myChildren.begin ( ) ; it! = myChildren.end ( ) ; it++ ) {
char c = ( * it) .first ;
PTrieNode child = ( * it) .second ;
child- > print( out, prefix+ c) ;
}
}
friend ostream& operator<< ( ostream& out, const Trie& node) {
node.print ( out, /*prefix=*/ "" ) ;
return out;
}
} ;
int main( ) {
Trie t;
string word;
while ( ! cin .eof ( ) ) {
cin >> word;
t.add ( word.c_str ( ) ) ;
cout << t << endl;
}
}
LyoqCiAqIFRyaWUgLSBhIHRyZWUgZm9yIGtlZXBpbmcgYSBzZXQgb2Ygd29yZHMsIGZhY3RvcmluZyBvdXQgZHVwbGljYXRlIHByZWZpeGVzLgogKiBEZW1vIGFwcGxpY2F0aW9uIC0ga2VlcCBhIHNvcnRlZCBzZXQgb2Ygd29yZHMuCiAqCiAqIElOUFVUOiBhIGxpc3Qgb2Ygd29yZHMuCiAqIE9VVFBVVDogdGhlIHNhbWUgbGlzdCwgc29ydGVkIGFuZCB3aXRob3V0IGR1cGxpY2F0ZXMuCiAqIAogKiBBdXRob3I6IEVyZWwgU2VnYWwKICogQ3JlYXRlZDogMjAxMC0xMC0xNAogKi8KCiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgpjbGFzcyBUcmllOwp0eXBlZGVmIFRyaWUqIFBUcmllTm9kZTsKCmNsYXNzIFRyaWUgewogIG1hcDxjaGFyLFBUcmllTm9kZT4gbXlDaGlsZHJlbjsKICBib29sIGlzV29yZEVuZDsgIC8vICJ0cnVlIiBpZiBhIHdvcmQgZW5kcyBpbiB0aGlzIG5vZGUKCnB1YmxpYzoKICAKICBUcmllKCk6IGlzV29yZEVuZChmYWxzZSkge30KCiAgLyogcmVjdXJzaXZlbHkgYWRkIGEgc2luZ2xlIHdvcmQgdG8gdGhlIG5vZGUgKi8KICB2b2lkIGFkZCAoY29uc3QgY2hhciogbmV3V29yZCkgewogICAgY2hhciBmaXJzdCA9IG5ld1dvcmRbMF07CiAgICBpZiAoIWZpcnN0KSB7IC8vIGVtcHR5IHdvcmQKICAgICAgaXNXb3JkRW5kID0gdHJ1ZTsKICAgIH0gZWxzZSB7CiAgICAgIGlmICghbXlDaGlsZHJlbltmaXJzdF0pIHsKICAgICAgICBteUNoaWxkcmVuW2ZpcnN0XSA9IG5ldyBUcmllKCk7CiAgICAgIH0KICAgICAgbXlDaGlsZHJlbltmaXJzdF0tPmFkZChuZXdXb3JkKzEpOwogICAgfQogIH0KCiAgLyogcmVjdXJzaXZlbHkgcHJpbnQgYWxsIHdvcmRzIGluIHRoZSBub2RlIGluIG9yZGVyICovCiAgdm9pZCBwcmludCAob3N0cmVhbSYgb3V0LCBzdHJpbmcgcHJlZml4KSBjb25zdCB7CiAgICBpZiAoaXNXb3JkRW5kKSB7CiAgICAgIG91dCA8PCBwcmVmaXggPDwgIiAiOwogICAgfQoKICAgIG1hcDxjaGFyLFBUcmllTm9kZT46OmNvbnN0X2l0ZXJhdG9yIGl0OwogICAgZm9yIChpdD1teUNoaWxkcmVuLmJlZ2luKCkgOyBpdCE9bXlDaGlsZHJlbi5lbmQoKTsgaXQrKykgewogICAgICBjaGFyIGMgPSAoKml0KS5maXJzdDsKICAgICAgUFRyaWVOb2RlIGNoaWxkID0gKCppdCkuc2Vjb25kOwogICAgICBjaGlsZC0+cHJpbnQob3V0LCBwcmVmaXgrYyk7CiAgICB9CiAgfQoKICBmcmllbmQgb3N0cmVhbSYgb3BlcmF0b3I8PCAob3N0cmVhbSYgb3V0LCBjb25zdCBUcmllJiBub2RlKSB7CiAgICBub2RlLnByaW50KG91dCwgLypwcmVmaXg9Ki8iIik7CiAgICByZXR1cm4gb3V0OwogIH0KfTsKCgoKaW50IG1haW4oKSB7CiAgVHJpZSB0OwogIHN0cmluZyB3b3JkOwogIHdoaWxlICghY2luLmVvZigpKSB7CiAgICBjaW4gPj4gd29yZDsKICAgIHQuYWRkKHdvcmQuY19zdHIoKSk7CiAgICBjb3V0IDw8IHQgPDwgZW5kbDsKICB9Cn0KCgo=