#include<iostream>
	#include<map>
	#include<vector>
	#include<string>

	typedef std::string         Word_t;
	typedef unsigned int        WordPosition_t;
	typedef unsigned int        IDdocument_t;

	typedef std::pair<IDdocument_t, WordPosition_t> DocumentPosition_t;
	typedef std::vector<DocumentPosition_t> WordReferences_t;

	WordReferences_t _intersect_two_words(const WordReferences_t& v1, const WordReferences_t& v2)
	{
		// all the locations where the words occur one after the other.
		WordReferences_t intersection;

		auto firstIt = v1.begin();
		auto secondIt = v2.begin();
		while (firstIt != v1.end() && secondIt != v2.end())
		{
			if (firstIt->first < secondIt->first)
			{
				++firstIt;
				continue;
			}
			// find the second word in the same document and AFTER the first word.
			if (secondIt->first < firstIt->first || secondIt->second < firstIt->second + 1)
			{
				++secondIt;
				continue;
			}
			// first word wasn't just before the second, it's not a phrase.
			if (secondIt->second > firstIt->second + 1)
			{
				++firstIt;
				continue;
			}
			// We found a phrase.
			intersection.emplace_back(*firstIt);
			++firstIt;
			++secondIt;
		}

		return intersection;
	}

	int main()
	{
		WordReferences_t v1, v2;
		v1.push_back(std::make_pair(10, 5));
		v1.push_back(std::make_pair(10, 25));
		v1.push_back(std::make_pair(11, 10));
		v1.push_back(std::make_pair(12, 1));
		v1.push_back(std::make_pair(12, 11));
		v1.push_back(std::make_pair(12, 21));
		v1.push_back(std::make_pair(12, 31));
		v1.push_back(std::make_pair(15, 11));
		v1.push_back(std::make_pair(100, 1));
		v1.push_back(std::make_pair(100, 11));
		v1.push_back(std::make_pair(100, 21));
		v1.push_back(std::make_pair(101, 11));
		v1.push_back(std::make_pair(102, 11));
		v1.push_back(std::make_pair(102, 13));
		v1.push_back(std::make_pair(102, 14));
		v1.push_back(std::make_pair(103, 11));
		v1.push_back(std::make_pair(103, 13));

		v2.push_back(std::make_pair(10, 11));
		v2.push_back(std::make_pair(12, 10));
		v2.push_back(std::make_pair(12, 40));
		v2.push_back(std::make_pair(16, 11));
		v2.push_back(std::make_pair(100, 12)); // match
		v2.push_back(std::make_pair(101, 12)); // match
		v2.push_back(std::make_pair(101, 13));
		v2.push_back(std::make_pair(101, 14));
		v2.push_back(std::make_pair(102, 12)); //match
		v2.push_back(std::make_pair(103, 1));
		v2.push_back(std::make_pair(103, 10));
		v2.push_back(std::make_pair(103, 12)); // match
		v2.push_back(std::make_pair(103, 15));

		auto intersection = _intersect_two_words(v1, v2);
		for (auto entry : intersection)
		{
			std::cout << entry.first << ", " << entry.second << "+" << (entry.second + 1) << std::endl;
		}

		return 0;
	}