fork download
copy 
  1. #include <string>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <climits>
  5. #include <array>
  6. #include <vector>
  7.  
  8. using iter_type = std::string::const_iterator;
  9.  
  10. iter_type find_pattern_in(iter_type txt_beg, iter_type txt_end, 
  11.                           iter_type pat_beg, iter_type pat_end)
  12. {
  13.     const unsigned txt_len = txt_end - txt_beg;
  14.     const unsigned pat_len = pat_end - pat_beg;
  15.  
  16.     // boyer-moore-horspool
  17.     if (txt_len >= pat_len)
  18.     {
  19.         std::array<int, UCHAR_MAX>  shift;
  20.         shift.fill(-1);
  21.  
  22.         for (unsigned i = 0; i < pat_len - 1; ++i)
  23.             shift[static_cast<unsigned char>(pat_beg[i])] = i;
  24.  
  25.         unsigned i = 0;
  26.         unsigned m = pat_len;
  27.  
  28.         while (i <= txt_len - pat_len)
  29.         {
  30.             int j = pat_len - 1;
  31.  
  32.             while (j >= 0 && pat_beg[j] == txt_beg[i + j])
  33.                 --j;
  34.  
  35.             if (j < 0)
  36.                 return txt_beg + i;
  37.  
  38.             i += pat_len - 1;
  39.             i -= shift[static_cast<unsigned char>(txt_beg[i])];
  40.         }
  41.     }
  42.  
  43.     return txt_end;
  44. }
  45.  
  46. iter_type find_pattern(const std::string& text, std::string pattern)
  47. {
  48.     // * in the pattern indicates a match of 0 to any number of characters.
  49.     // \* indicates a literal match for the asterisk.
  50.  
  51.     std::vector<std::string> pats;  // list of literal patterns which must occur in
  52.                                     // text, consecutively and with no overlap
  53.  
  54.     {
  55.         unsigned last_pos = 0;
  56.         unsigned pos = 0;
  57.         while ((pos = pattern.find('*', pos)) != std::string::npos)
  58.         {
  59.             if (pos == 0 || pattern[pos - 1] == '\\')
  60.                 pattern.erase(pos ? pos - 1 : pos, 1);
  61.             else
  62.             {
  63.                 pats.emplace_back(pattern.substr(last_pos, pos - last_pos));
  64.                 last_pos = ++pos;
  65.             }
  66.         }
  67.  
  68.         if (last_pos < pattern.length())
  69.             pats.emplace_back(pattern.substr(last_pos));
  70.     }
  71.  
  72.     iter_type last_loc = text.end();
  73.     iter_type loc = text.begin();
  74.     for (auto& pat : pats)
  75.     {
  76.         last_loc = loc = find_pattern_in(loc, text.end(), pat.begin(), pat.end());
  77.         if (loc == text.end())
  78.             return text.end();
  79.  
  80.         loc += pat.length();
  81.     }
  82.  
  83.     return last_loc;
  84. }
  85.  
  86. #include <sstream>
  87. std::istringstream in(  // text,pattern
  88. R"(Hello,ell
  89. This is good, is
  90. Mothra,M*ra
  91. Old,Young
  92. bY T,Y T
  93. lnHLp5kGMHeYsoA7NXFrL8Ij Su,S
  94. f3SFw5trxxZIaKec,wa3fZceFxS
  95. )"
  96. );
  97.  
  98. int main(int argc, char* argv[])
  99. {
  100.     // std::ifstream in(argv[1]);
  101.  
  102.     std::string text, pattern;
  103.  
  104.     while (std::getline(in, text, ',') && std::getline(in, pattern))
  105.         std::cout << (text.end() != find_pattern(text, pattern) ? "true\n" : "false\n");
  106. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
true
false
true
true
false
https://ideone.com/lWCUrs
language:
C++14 (gcc 8.3)
created:
10 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!