#include<vector>
	#include<algorithm>
	#include<string>
	#include<iterator>

	class cross_word_db
	{
	protected:
		std::vector<std::vector<size_t> > wordlookups;
		std::vector<std::string> words;
		//an array that is 26*wordlength long basically a double array.
		//...it stores another array of sorted indices (a set in linear memory)
		
		static size_t lookupdex(size_t p,const char c)
		{
			return p*26+std::tolower(c);
		}
	public:
		
		template<class Iter>
		cross_word_db(Iter b,Iter e):
			words(b,e)
		{
			size_t max_wordlength=0;
			
			for(size_t i=0;i<words.size();i++)
			{
				if(words[i].size() > max_wordlength)
				{
					max_wordlength=words[i].size();
				}
			}//find the longest word
			
			wordlookups.resize(26*max_wordlength);
			
			//build the database...
			for(size_t i=0;i<words.size();i++)
			{
				const std::string& w=words[i];
				//for each letter, push that words's index into the correct location.
				//this will be in sorted order by default.
				for(size_t pos=0;pos<w.size();pos++)
				{
					wordlookups[lookupdex(pos,w[i])].push_back(i); 
				}
			}
		}
		//a constraint is a 'position,character' pair
		typedef std::pair<std::size_t,char> query_constraint;
		
		//a query takes a list of query_constraints...this could have also been an iterator, but whatever
		std::vector<std::string> query(const std::vector<query_constraint>& query) const
		{
			std::vector<query_constraint>::const_iterator qbegin,qend;
			qbegin=query.cbegin();
			qend=query.cend();
			std::vector<size_t> result=wordlookups[lookupdex(qbegin->first,qbegin->second)];
			while((++qbegin) != qend)
			{
				std::vector<size_t> old_result=result;
				const std::vector<size_t>& qlist=wordlookups[lookupdex(qbegin->first,qbegin->second)];
				std::vector<size_t>::iterator last=set_intersect(old_result.begin(),old_result.end(),qlist.begin(),qlist.end(),result.begin());
				result.resize(last-result.begin());
			}
			std::vector<std::string> retval(result.size());
			for(size_t i=0;i<result.size();i++)
			{
				retval[i]=words[result[i]];
			}
			return retval;
		}
	};