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 std::map<size_t,size_t> hash_map;
  12. typedef std::vector<std::string> wordlist;
  13.  
  14. size_t ordered_symbol( hash_map &h, std::string const& word )
  15. {
  16.     std::hash<std::string> hash_fn;
  17.     size_t hash = hash_fn(word);
  18.     if(h.find(hash)==h.end())
  19.     {
  20.         size_t const sequence = h.size();
  21.         h[hash] = sequence;
  22.         return sequence;
  23.     }
  24.     return h[hash];
  25. }
  26.  
  27. wordlist create_wordlist( std::string const& str )
  28. {
  29.     if(str.find_first_of(' ') != std::string::npos)
  30.     {
  31.         wordlist w1;
  32.         std::stringstream sstr(str);
  33.         std::string s;
  34.         while(sstr>>s)
  35.             w1.push_back(s);
  36.         return w1;        
  37.     }
  38.     wordlist w2;
  39.     for(auto i : str)
  40.     {
  41.         std::string s;
  42.         s.append(1,i);
  43.         w2.push_back(s);
  44.     }
  45.     return w2;
  46. }
  47.  
  48. bool pattern_matches( std::string const& s1, std::string const& s2 )
  49. {
  50.     wordlist const w1 = create_wordlist(s1);
  51.     wordlist const w2 = create_wordlist(s2);
  52.     if(w1.size()!=w2.size())
  53.         return false;
  54.     hash_map h1,h2;
  55.     for( size_t i = 0; i!=w1.size(); ++i)
  56.         if(ordered_symbol(h1,w1[i])!=ordered_symbol(h2,w2[i]))
  57.             return false;
  58.     return true;
  59. }
  60.  
  61. void test( std::string const& s1, std::string const& s2 )
  62. {
  63.     std::cout<<"["<<s1<<"] "
  64.              <<(pattern_matches(s1,s2)? "<==>" : "<=!=>")
  65.              <<"["<<s2<<"]\n";    
  66. }
  67.  
  68. int main()
  69. {
  70.     test("red blue blue red red yellow","abbaac");
  71.     test("red blue blue red red yellow","first second second first first third");
  72.     test("abbaac","12211g");
  73.     test("abbaac","red blue blue red red yellow");
  74.     test("abbgac","red blue blue red red yellow");
  75.     return 0;
  76. }
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/T2D4xT
language:
C++14 (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!