Find the longest word in a list made of other words in that list.

longest_made_of_others.cpp

template<typename Iterator>
class LongestOfOthers
{
public:
	
	using T = typename std::iterator_traits<Iterator>::value_type;
	
	Iterator operator()(Iterator begin, Iterator end)
	{
		if (begin == end) return end;
		
		_words.clear();
		_words.insert(begin, end);
		
		Iterator longest = end;
		
		for ( ; begin != end; ++begin)
		{
			if (longest == end || begin->size() > longest->size())
			{
				if (_made_of_others(*begin, begin->begin()))
				{
					 longest = begin;
				}
			}
		}
		
		return longest;
	}
	
private:
	
	bool _made_of_others(const std::string& word,
						 std::string::const_iterator first)
	{
		if (first == word.end()) return true;
		
		std::string substring;
		
		for (auto last = word.end(); first != last; ++first)
		{
			substring += *first;
			
			if (_words.count(substring) && substring != word)
			{
				if (_made_of_others(word, std::next(first)))
				{
					return true;
				}
			}
		}
		
		return false;
	}
	
	std::unordered_set<T> _words;
};

template<typename Iterator>
Iterator longest_made_of_others(Iterator begin, Iterator end)
{
	LongestOfOthers<Iterator> find;
	
	return find(begin, end);
}