/* The idea behind this solution is that for a given prefix,
 * all words beginning with the prefix must come
 * lexicographically after the prefix and before the prefix
 * formed by increasing the last letter by one.  For example,
 * all words starting with "abd" come between "adb" and "abe."
 * Using this, we get this solution:
 */
void PrintMatchingPrefixes(set<string>& words, string prefix)
{
	/* Edge case: if the prefix is empty, everything matches. */
	if (prefix.empty())
		copy(words.begin(), words.end(), ostream_iterator<string>(cout, "\n"));
	else
	{
		/* Construct the stop prefix. */
		string stopPrefix = prefix;
		++stopPrefix[stopPrefix.size() - 1];
		
		/* Use lower_bound to denote the proper range. */
		copy(words.lower_bound(prefix), words.lower_bound(stopPrefix),
		     ostream_iterator<string>(cout, "\n"));
	}
}