Task: Word Chains (International Olympiad in Informatics)

question.md

Task: Word Chains

source: International Olympiad in Informatics

A word consists of at least one and at most 75 lowercase letters (from a to z). A list of one or more words is called a chain when each word in that list, except the first, is obtained from the preceding word by appending one or more letters on the right. For instance, the list

i
in
int
integer

is a chain of four words, but the list

input
integer

is not a chain. Note that every list of one word is a chain.

Input Data

Your program is given a list of words in the file INPUT.TXT. This list contains at least one word and all of the words together have no more than 2,000,000 letters. The input is terminated with a line containing a single period (`.'). All other lines contain one word each. The list is sorted lexicographically using the standard alphabetical ordering (as in an English dictionary). There are no duplicate words in the list.

Output Data

The length of a chain is the number of words it contains. Your program should write to file OUTPUT.TXT a longest chain of words taken from the input. Each word should be on a separate line. If there is more than one chain of maximum length, your program should output only one of these chains. It does not matter which one. Example Input and Output Figure 1 gives an input file with seven words and the corresponding output file. The input contains one chain of length four and no chains with more than four words.

____________    _____________
|INPUT.TXT |    |OUTPUT.TXT |
|__________|    |___________|
|i         |    |i          |
|if        |    |in         |
|in        |    |int        |
|input     |    |integer    |
|int       |    |___________|
|integer   |                 
|output    |                 
|.         |                 
|__________|

Figure 1: Example input and output

wordChains.cpp

// ref: http://ioinformatics.org/locations/ioi95/contest/tasks/chain.shtml
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

class Node {
public:
	// members
	string val;
	vector<Node*> children;

	// constructor
	Node(string val) {
		this->val = val;
	}

	// destructor
	virtual ~Node() {
		for (int i=0 ; i < children.size() ; i++) {
			delete children[i];
		}
	}

	// methods
	bool insert(Node* n) {
		// TODO: validation

		// check whether val starts with n->val
		if (n->val.compare(0, val.size(), val) != 0) {
			return false;
		}

		bool inserted = false;
		for (int i=0 ; i < children.size() && !inserted ; i++) {
			inserted = children[i]->insert(n);
		}

		if (!inserted) {
			children.push_back(n);
		}

		return true;
	}

	pair<int,vector<string> > getLongestPathRecursive() {
		if (children.size() == 0) {
			return pair<int, vector<string> > (1,  vector<string>(1,val));
		}

		pair<int, vector<string> > max(0, vector<string>());

		for (int i=0 ; i < children.size() ; i++) {
			pair<int, vector<string> > tmp = children[i]->getLongestPathRecursive();
			if (tmp.first > max.first) {
				max = tmp;
			}
		}

		(max.second).push_back(val);
		max.first++;

		return max;
	}

	pair<int,vector<string> > getLongestPathIterative() {
			if (children.size() == 0) {
				return pair<int, vector<string> > (1,  vector<string>(1,val));
			}

			pair<int, vector<string> > max(0, vector<string>());

			queue< pair<Node* ,vector<string> > > q;
			q.push(pair<Node* ,vector<string> >(this, vector<string>()));

			while(!q.empty()) {
				pair<Node* ,vector<string> > next = q.front();
				q.pop();

				vector<string> path(next.second);
				path.push_back(next.first->val);

				if (max.first < path.size()) {
					max.first = path.size();
					max.second = path;
				}

				for (int i=0 ; i < next.first->children.size() ; i++) {
					q.push(pair<Node* ,vector<string> >(next.first->children[i], path));
				}
			}

			return max;
		}

	void printLongestPathRecursive() {
		vector<string> path = getLongestPathRecursive().second;

		for (int i=path.size()-1 ; i >=0 ; i--) {
			cout << path[i] << endl;
		}
	}

	void printLongestPathIterative() {
		vector<string> path = getLongestPathIterative().second;

		for (int i=0 ; i < path.size() ; i++) {
			cout << path[i] << endl;
		}
	}
};

int main() {
	vector<string> input;
	input.push_back("j");
	input.push_back("i");
	input.push_back("it");
	input.push_back("if");
	input.push_back("ita");
	input.push_back("in");
	input.push_back("input");
	input.push_back("int");
	input.push_back("integer");
	input.push_back("output");

	/* Build tree. */
	Node* root = new Node("");
	for (int i=0 ; i < input.size() ; i++) {
		root->insert(new Node(input[i]));
	}

	root->printLongestPathIterative();

	delete root;
}