/**
* Trie - a tree for keeping a set of words, factoring out duplicate prefixes.
* Demo application - find the shortest set of operations for printing a given set of words.
*
* INPUT: a number N, and a list of N words.
* OUTPUT: the length of the shortest sequence of operations, and one such sequence.
*
* @author Erel Segal http://t...content-available-to-author-only...s.fm/rentabrain
* @date 2010-10-14
*/
#include <map>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
using namespace std;
class Trie;
typedef Trie* PTrieNode;
typedef unsigned long ulong;
string randomWord(int length) { // for testing
string r="";
for (int i=0; i<length; ++i) {
char c = 'a'+rand()%26;
r+=c;
}
return r;
}
// A Trie for holding words above [a-z]
class Trie {
PTrieNode myChildren[26]; // non-capitals only!
unsigned int wordCount; // number of words contained in this node
// keep a record of the longest word in this Trie.
// It should be printed at the end, because we don't care about letters remaining in the printer.
int myLongestWordLength;
short myLongestWordPrefix;
public:
Trie(): wordCount(0), myLongestWordLength(0), myLongestWordPrefix(0) {
fill_n(myChildren, 26, (PTrieNode)NULL);
}
/* recursively add a single word to the node */
void add (const char* newWord) {
// add the word:
char first = newWord[0];
if (!first) { // end of word
++wordCount; // add 1 to the number of words ending here
} else {
if ('a'<=first && first <= 'z') {
if (!myChildren[first-'a']) {
myChildren[first-'a'] = new Trie();
}
myChildren[first-'a']->add(newWord+1);
}
// keep track of the longest word:
int len = strlen(newWord);
if (len > myLongestWordLength) {
myLongestWordLength = len;
myLongestWordPrefix = first-'a';
}
}
}
void addWords(istream& in) {
int wordCount;
in >> wordCount;
string word;
for (int i=0; i<wordCount; ++i) {
in >> word;
add(word.c_str());
}
}
void addRandomWords(int wordCount, int wordLength) {
for (int i=0; i<wordCount; ++i) {
add(randomWord(wordLength).c_str());
}
}
/* recursively print a minimal set of printer operations needed to print the set of words.
[a..z] = add a letter.
- = remove a letter.
P = print the current word.
*/
void printOperations (ostream& out, bool topLevel=true) const {
for (unsigned int i=0; i<wordCount; ++i) {
out << "P";
}
for (int i=0; i<26; ++i) {
char c = i+'a';
if (i==myLongestWordPrefix) continue; // print it at the end
PTrieNode child = myChildren[i];
if (child) {
out << c;
child->printOperations(out, /*topLevel=*/false);
out << "-";
}
}
if (myLongestWordLength) {
out << (char)(myLongestWordPrefix+'a');
myChildren[myLongestWordPrefix]->printOperations(out, topLevel);
if (!topLevel) out << "-";
}
}
};
void test(string input, string expected) {
stringstream in(input);
Trie t;
time_t before = time(NULL);
t.addWords(in);
stringstream operationStream;
t.printOperations(operationStream);
string a = operationStream.str();
if (a!=expected) {
cerr << "ERROR: operations for '" << input << "' should be " << expected << " but was " << a << endl;
} else {
time_t after = time(NULL);
cout << "calculated cost of " << input.size() << " chars in " << (after-before) << " seconds" << endl;
}
}
void testRandom(int wordCount, int wordLength) {
Trie t;
time_t before = time(NULL);
t.addRandomWords(wordCount, wordLength);
stringstream operationStream;
t.printOperations(operationStream);
string a = operationStream.str();
time_t after = time(NULL);
cout << "calculated cost of " << wordLength << "x" << wordCount << " chars in " << (after-before) << " seconds" << endl;
if (a.length()<2000)
cout << "result=" << a << endl;
}
int main() {
//test("3 print the poem", "theP---poemP---rintP");
//test("3 arint the aoem", "theP---aoemP---rintP");
//testRandom(50,20);
//return 1;
Trie t;
t.addWords(cin);
stringstream operationStream;
t.printOperations(operationStream);
string operations = operationStream.str();
unsigned long operationsCount = operations.length();
cout << operationsCount << endl;
for (unsigned long i=0; i<operationsCount; ++i) {
cout << operations[i] << endl;
}
}