fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <sstream>
  6. /*
  7. s1 = "red blue blue red red yellow"
  8. s2 = "abbaac"
  9. This would match because they have the same pattern.
  10. */
  11. typedef size_t hash_type;
  12. typedef std::map<hash_type,size_t> hash_map;
  13. typedef std::vector<std::string> wordlist;
  14.  
  15. //taken from http://stackoverflow.com/a/8317622/13760
  16. #define A 54059 /* a prime */
  17. #define B 76963 /* another prime */
  18. #define C 86969 /* yet another prime */
  19. size_t hash(const char* s)
  20. {
  21.    size_t h = 31 /* also prime */;
  22.    while (*s) {
  23.      h = (h * A) ^ (s[0] * B);
  24.      s++;
  25.    }
  26.    return h; // or return h % C;
  27. }
  28. #undef A
  29. #undef B
  30. #undef C
  31.  
  32. size_t ordered_symbol( hash_map &h, std::string const& word )
  33. {
  34.     hash_type word_hash = hash(word.c_str());
  35.     if(h.find(word_hash)==h.end())
  36.     {
  37.         size_t const sequence = h.size();
  38.         h[word_hash] = sequence;
  39.         return sequence;
  40.     }
  41.     return h[word_hash];
  42. }
  43.  
  44. wordlist create_wordlist( std::string const& str )
  45. {
  46.     if(str.find_first_of(' ') != std::string::npos)
  47.     {
  48.         wordlist w1;
  49.         std::stringstream sstr(str);
  50.         std::string s;
  51.         while(sstr>>s)
  52.             w1.push_back(s);
  53.         return w1;        
  54.     }
  55.     wordlist w2;
  56.     for(size_t i=0; i!=str.length();++i)
  57.     {
  58.         std::string s;
  59.         s.append(1,str[i]);
  60.         w2.push_back(s);
  61.     }
  62.     return w2;
  63. }
  64.  
  65. bool pattern_matches( std::string const& s1, std::string const& s2 )
  66. {
  67.     wordlist const w1 = create_wordlist(s1);
  68.     wordlist const w2 = create_wordlist(s2);
  69.     if(w1.size()!=w2.size())
  70.         return false;
  71.     hash_map h1,h2;
  72.     for( size_t i = 0; i!=w1.size(); ++i)
  73.         if(ordered_symbol(h1,w1[i])!=ordered_symbol(h2,w2[i]))
  74.             return false;
  75.     return true;
  76. }
  77.  
  78. void test( std::string const& s1, std::string const& s2 )
  79. {
  80.     std::cout<<"["<<s1<<"] "
  81.              <<(pattern_matches(s1,s2)? "<==>" : "<=!=>")
  82.              <<"["<<s2<<"]\n";    
  83. }
  84.  
  85. int main()
  86. {
  87.     test("red blue blue red red yellow","abbaac");
  88.     test("red blue blue red red yellow","first second second first first third");
  89.     test("abbaac","12211g");
  90.     test("abbaac","red blue blue red red yellow");
  91.     test("abbgac","red blue blue red red yellow");
  92.     return 0;
  93. }
Success #stdin #stdout 0s 2992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[red blue blue red red yellow] <==>[abbaac]
[red blue blue red red yellow] <==>[first second second first first third]
[abbaac] <==>[12211g]
[abbaac] <==>[red blue blue red red yellow]
[abbgac] <=!=>[red blue blue red red yellow]
https://ideone.com/QGMMB9
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!