//R. Andrew Lamonica
//Falling Words 


#include <fstream>
#include <iostream>
#include <string>
#include <map>
#include <locale>

using namespace std;

typedef map<string,string>  word_list;



void displayWord(string word, word_list lists[])
{
	cout << "(" << word;
	int i,
	    len = word.length()-1;
	string childLst = lists[len+1][word];
	for(i=0; i<childLst.length(); i+=len)
	{
		displayWord(childLst.substr(i,len), lists);
		if(i+len<childLst.length())
				cout << " ";
	}
	cout << ")";
}

void displayWords(int length, word_list lists[])
{
	for(word_list::iterator i=lists[length].begin(); i!=lists[length].end(); i++)
	{
		displayWord(i->first, lists);
		cout << endl;
/*		cout << i->first;
		int ancest = length-1;
		string parent = i->second;
		while(ancest)
		{
			cout << " " << parent;
			parent = lists[ancest][parent.substr(0,ancest)];
			ancest--;
		}
		cout << endl;
*/
	}
}
	
int main()
{
	ifstream dict("/usr/share/dict/words");
	string word;
	word_list lists[128];
	int longest = 1;
	
	//Load Words
	while(dict >> word)
	{
		if(islower(word[0]))
		{
			int len = word.length();
			lists[len][word] = "";
			if(len>longest)
				longest=len;
		}
	}
	//One Letter
	lists[1]["a"] = "";
	lists[1]["i"] = "";
	
	int wordLen, 
	    removedLetter;
	for(wordLen=2; wordLen<=longest && !lists[wordLen-1].empty(); wordLen++)
	{
		word_list::iterator i;
		for(i=lists[wordLen].begin(); i!=lists[wordLen].end(); i++)
		{
			for(removedLetter=0; removedLetter<wordLen; removedLetter++)
			{
				string testWord = i->first.substr(0,removedLetter) + i->first.substr(removedLetter+1);
				if(lists[wordLen-1].end() != lists[wordLen-1].find(testWord))
				{
					if(i->second.empty())
						i->second = testWord;
					else
						i->second += testWord;
				}
			}
		}
		//Remove Bad Ones
		i = lists[wordLen].begin();
		while(i!=lists[wordLen].end())
		{
			if(i->second.empty())
			{
				word_list::iterator last = i;
				i++;
				lists[wordLen].erase(last);
			}
			else
				i++;
		}
		cout << wordLen << " - Done (Found: " << lists[wordLen].size() << ")" << endl;
	}

	
	
	displayWords(wordLen-2, lists);
	displayWords(wordLen-3, lists);
	return 0;
}