/* 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()) {
		for (set<string>::iterator itr = words.begin(); itr != words.end(); ++itr)
			cout << *itr << endl;
	} else {
		/* Construct the stop prefix. */
		string stopPrefix = prefix;
		++stopPrefix[stopPrefix.size() - 1];
		
		/* Use lower_bound to denote the proper range. */
		for (set<string>::iterator itr = words.lower_bound(prefix); itr != words.lower_bound(stopPrefix); ++itr)
			cout << *itr  << endl;
	}
}