fork download
copy 
  1.     #include<vector>
  2. 	#include<algorithm>
  3. 	#include<string>
  4. 	#include<iterator>
  5.  
  6. 	class cross_word_db
  7. 	{
  8. 	protected:
  9. 		std::vector<std::vector<size_t> > wordlookups;
  10. 		std::vector<std::string> words;
  11. 		//an array that is 26*wordlength long basically a double array.
  12. 		//...it stores another array of sorted indices (a set in linear memory)
  13.  
  14. 		static size_t lookupdex(size_t p,const char c)
  15. 		{
  16. 			return p*26+std::tolower(c);
  17. 		}
  18. 	public:
  19.  
  20. 		template<class Iter>
  21. 		cross_word_db(Iter b,Iter e):
  22. 			words(b,e)
  23. 		{
  24. 			size_t max_wordlength=0;
  25.  
  26. 			for(size_t i=0;i<words.size();i++)
  27. 			{
  28. 				if(words[i].size() > max_wordlength)
  29. 				{
  30. 					max_wordlength=words[i].size();
  31. 				}
  32. 			}//find the longest word
  33.  
  34. 			wordlookups.resize(26*max_wordlength);
  35.  
  36. 			//build the database...
  37. 			for(size_t i=0;i<words.size();i++)
  38. 			{
  39. 				const std::string& w=words[i];
  40. 				//for each letter, push that words's index into the correct location.
  41. 				//this will be in sorted order by default.
  42. 				for(size_t pos=0;pos<w.size();pos++)
  43. 				{
  44. 					wordlookups[lookupdex(pos,w[i])].push_back(i); 
  45. 				}
  46. 			}
  47. 		}
  48. 		//a constraint is a 'position,character' pair
  49. 		typedef std::pair<std::size_t,char> query_constraint;
  50.  
  51. 		//a query takes a list of query_constraints...this could have also been an iterator, but whatever
  52. 		std::vector<std::string> query(const std::vector<query_constraint>& query) const
  53. 		{
  54. 			std::vector<query_constraint>::const_iterator qbegin,qend;
  55. 			qbegin=query.cbegin();
  56. 			qend=query.cend();
  57. 			std::vector<size_t> result=wordlookups[lookupdex(qbegin->first,qbegin->second)];
  58. 			while((++qbegin) != qend)
  59. 			{
  60. 				std::vector<size_t> old_result=result;
  61. 				const std::vector<size_t>& qlist=wordlookups[lookupdex(qbegin->first,qbegin->second)];
  62. 				std::vector<size_t>::iterator last=set_intersect(old_result.begin(),old_result.end(),qlist.begin(),qlist.end(),result.begin());
  63. 				result.resize(last-result.begin());
  64. 			}
  65. 			std::vector<std::string> retval(result.size());
  66. 			for(size_t i=0;i<result.size();i++)
  67. 			{
  68. 				retval[i]=words[result[i]];
  69. 			}
  70. 			return retval;
  71. 		}
  72. 	};
  73.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rCmyZn
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!