/*
 * add-a-gram.cpp : Solve the "Add-A-Gram" puzzle
 *
 * Copyright (c) 2002 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * See http://www.itasoftware.com/careers/puzzle_archive.html
 *
 *   Add-A-Gram
 *
 *     An "add-a-gram" is a sequence of words formed by starting with a
 *     3-letter word, adding a letter and rearranging to form a 4-letter word,
 *     and so on. For example, here are add-a-grams of the words "CREDENTIALS"
 *     and "ANACHRONISM":
 *
 *       ail + s =                           mar + c =
 *       sail + n =                          cram + h =
 *       nails + e =                         march + s =
 *       aliens + t =                        charms + o =
 *       salient + r =                       chromas + n =
 *       entrails + c =                      monarchs + i =
 *       clarinets + e =                     harmonics + a =
 *       interlaces + d =                    maraschino + n =
 *       CREDENTIALS (length 11)             ANACHRONISM (length 11)
 *
 *     Test your own credentials: given the dictionary found here[1],
 *     what is the longest add-a-gram?
 *
 * [1] http://www.itasoftware.com/careers/work-at-ita/PuzzleFiles/WORD.LST
 *     a copy is preserved on http://www.benzedrine.ch/WORD.LST (1.7M)
 *     MD5 (WORD.LST) = e942e9e884090d2bdb02265864882231
 *
 */

#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;

struct size_compare {
	bool operator() (const string &a, const string &b) const {
		return a.size() <= b.size();
	}	
};

unsigned recurse(const string &, const map<string, string> &, stack<string> &);

int main()
{
	priority_queue<string, vector<string>, size_compare> q;
	map<string, string> m;
	stack<string> p;

	ifstream is("WORD.LST");
	string s;

	while (getline(is, s)) {
		q.push(s);
		string t = s;
		sort(t.begin(), t.end());
		m[t] = s;
	}

	while (!q.empty()) {
		if (recurse(q.top(), m, p)) {
			cout << q.top() << endl;
			break;
		}
		q.pop();
	}

	return 0;
}

unsigned recurse(const string &s, const map<string, string> &m, stack<string> &p)
{
	if (s.size() == 3) {
		while (!p.empty()) {
			cout << p.top() << endl;
			p.pop();
		}
		return 1;
	}

	string t, u;
	map<string, string>::const_iterator j;

	for (unsigned i = 0; i < s.size(); ++i) {
		t = s;
		t.erase(t.begin() + i);
		sort(t.begin(), t.end());

		if ((j = m.find(t)) != m.end()) {
			u = (*j).second + " + ";
			u.insert(u.end(), s[i]);
			p.push(u);
			if (recurse(t, m, p))
				return 1;
			p.pop();
		}
	}

	return 0;
}