Find the shortest distance between two words in string, optimized for many queries.

shortest-distance.cpp

class Lookup
{
public:
	
	using size_t = std::size_t;
	
	Lookup(const std::string& words)
	{
		reset(words);
	}
	
	Lookup(const std::vector<std::string>& words)
	{
		reset(words);
	}
	
	size_t operator()(const std::string& first,
					  const std::string& second) const
	{
		static const size_t maximum = std::numeric_limits<size_t>::max();
		
		if (first == second) return 0;
		
		auto first_indices = _indices.at(first);
		
		auto second_indices = _indices.at(second);
		
		size_t shortest = maximum;
		
		for (const auto& index : first_indices)
		{
			auto other = second_indices.lower_bound(index);
			
			if (other != second_indices.end())
			{
				auto distance = *other - index;
				
				if (distance < shortest) shortest = distance;
			}
			
			if (other != second_indices.begin())
			{
				auto distance = index - *(--other);
				
				if (distance < shortest) shortest = distance;
			}
		}
		
		return shortest;
	}
	
	void reset(const std::string& string)
	{
		reset(_split(string));
	}
	
	void reset(const std::vector<std::string>& words)
	{
		_indices.clear();
		
		for (std::size_t i = 0; i < words.size(); ++i)
		{
			_indices[words[i]].insert(i);
		}
	}

private:
	
	static std::vector<std::string> _split(const std::string& string)
	{
		std::vector<std::string> words;
		
		auto j = string.begin();
		
		auto end = string.end();
		
		do
		{
			auto i = std::find_if_not(j, end, ::isspace);
			
			j = std::find_if(i, end, ::isspace);
			
			words.push_back(std::string(i, j));
		}
		
		while (j++ != end);
		
		return words;
	}
	
	std::unordered_map<std::string, std::set<size_t>> _indices;
};