snipt

Ctrl+h for KB shortcuts

C++

Wildcard match

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

bool wildcardMatch(string &s1, string& pat, int i, int j) {
  if (i == s1.size()) return j == pat.size();
  char c1 = s1[i];
  char c2 = pat[j];
  if (c2 != '*' && c1 != c2) return false;
  else
    return wildcardMatch(s1,pat,i+1,j+1) || wildcardMatch(s1,pat,i+1,j);
}

int main() {
  string s1 = "readme.txt";
  string pat = "*.txt";
  bool result = wildcardMatch(s1,pat,0,0);
  cout << "matched?:" << result << endl;
  return 0;
}
https://snipt.net/embed/5c52c6353fed559c856321d2efe7487f/
/raw/5c52c6353fed559c856321d2efe7487f/
5c52c6353fed559c856321d2efe7487f
cpp
C++
24
2019-08-21T05:22:07
True
False
False
Nov 08, 2015 at 05:54 PM
/api/public/snipt/142293/
wildcard-match
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><a href="#L-1"> 1</a> <a href="#L-2"> 2</a> <a href="#L-3"> 3</a> <a href="#L-4"> 4</a> <a href="#L-5"> 5</a> <a href="#L-6"> 6</a> <a href="#L-7"> 7</a> <a href="#L-8"> 8</a> <a href="#L-9"> 9</a> <a href="#L-10">10</a> <a href="#L-11">11</a> <a href="#L-12">12</a> <a href="#L-13">13</a> <a href="#L-14">14</a> <a href="#L-15">15</a> <a href="#L-16">16</a> <a href="#L-17">17</a> <a href="#L-18">18</a> <a href="#L-19">19</a> <a href="#L-20">20</a> <a href="#L-21">21</a> <a href="#L-22">22</a> <a href="#L-23">23</a></pre></div></td><td class="code"><div class="highlight"><pre><span></span><span id="L-1"><a name="L-1"></a><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp"></span> </span><span id="L-2"><a name="L-2"></a><span class="cp">#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp"></span> </span><span id="L-3"><a name="L-3"></a><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span> </span><span id="L-4"><a name="L-4"></a><span class="cp">#include</span> <span class="cpf">&lt;stack&gt;</span><span class="cp"></span> </span><span id="L-5"><a name="L-5"></a> </span><span id="L-6"><a name="L-6"></a><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> </span><span id="L-7"><a name="L-7"></a> </span><span id="L-8"><a name="L-8"></a><span class="kt">bool</span> <span class="nf">wildcardMatch</span><span class="p">(</span><span class="n">string</span> <span class="o">&amp;</span><span class="n">s1</span><span class="p">,</span> <span class="n">string</span><span class="o">&amp;</span> <span class="n">pat</span><span class="p">,</span> <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-9"><a name="L-9"></a> <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">s1</span><span class="p">.</span><span class="n">size</span><span class="p">())</span> <span class="k">return</span> <span class="n">j</span> <span class="o">==</span> <span class="n">pat</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> </span><span id="L-10"><a name="L-10"></a> <span class="kt">char</span> <span class="n">c1</span> <span class="o">=</span> <span class="n">s1</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> </span><span id="L-11"><a name="L-11"></a> <span class="kt">char</span> <span class="n">c2</span> <span class="o">=</span> <span class="n">pat</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> </span><span id="L-12"><a name="L-12"></a> <span class="k">if</span> <span class="p">(</span><span class="n">c2</span> <span class="o">!=</span> <span class="sc">&#39;*&#39;</span> <span class="o">&amp;&amp;</span> <span class="n">c1</span> <span class="o">!=</span> <span class="n">c2</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> </span><span id="L-13"><a name="L-13"></a> <span class="k">else</span> </span><span id="L-14"><a name="L-14"></a> <span class="k">return</span> <span class="n">wildcardMatch</span><span class="p">(</span><span class="n">s1</span><span class="p">,</span><span class="n">pat</span><span class="p">,</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">||</span> <span class="n">wildcardMatch</span><span class="p">(</span><span class="n">s1</span><span class="p">,</span><span class="n">pat</span><span class="p">,</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">j</span><span class="p">);</span> </span><span id="L-15"><a name="L-15"></a><span class="p">}</span> </span><span id="L-16"><a name="L-16"></a> </span><span id="L-17"><a name="L-17"></a><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> </span><span id="L-18"><a name="L-18"></a> <span class="n">string</span> <span class="n">s1</span> <span class="o">=</span> <span class="s">&quot;readme.txt&quot;</span><span class="p">;</span> </span><span id="L-19"><a name="L-19"></a> <span class="n">string</span> <span class="n">pat</span> <span class="o">=</span> <span class="s">&quot;*.txt&quot;</span><span class="p">;</span> </span><span id="L-20"><a name="L-20"></a> <span class="kt">bool</span> <span class="n">result</span> <span class="o">=</span> <span class="n">wildcardMatch</span><span class="p">(</span><span class="n">s1</span><span class="p">,</span><span class="n">pat</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span> </span><span id="L-21"><a name="L-21"></a> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&quot;matched?:&quot;</span> <span class="o">&lt;&lt;</span> <span class="n">result</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span> </span><span id="L-22"><a name="L-22"></a> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-23"><a name="L-23"></a><span class="p">}</span> </span></pre></div> </td></tr></table>
match, recursion, string, wildcard
--- 
+++ 
@@ -0,0 +1,23 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <stack>
+
+using namespace std;
+
+bool wildcardMatch(string &s1, string& pat, int i, int j) {
+  if (i == s1.size()) return j == pat.size();
+  char c1 = s1[i];
+  char c2 = pat[j];
+  if (c2 != '*' && c1 != c2) return false;
+  else
+    return wildcardMatch(s1,pat,i+1,j+1) || wildcardMatch(s1,pat,i+1,j);
+}
+
+int main() {
+  string s1 = "readme.txt";
+  string pat = "*.txt";
+  bool result = wildcardMatch(s1,pat,0,0);
+  cout << "matched?:" << result << endl;
+  return 0;
+}