Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I felt bad for only <em>hinting</em> on backtracking and recursion in a comment. Here's an explanation:</p> <h3>Strategy:</h3> <p>Focus on the tokens <em>between</em> wilcards (the wildcards are not what should be matched).</p> <ul> <li>extract first token from pattern</li> <li>exit with success for no (more) tokens</li> <li>for each token match in input <ul> <li>match the remainder of the pattern against the remainder of the input</li> <li>if no successful submatch, fail, otherwise done</li> </ul></li> </ul> <p>There is recursion (the matching of the remainder class match(....) recursively).</p> <p>There is backtracking (if the recursive match doesn't succeed, we try the next token submatch)</p> <h3>Sample (<em>see <a href="https://ideone.com/yApYp" rel="nofollow">https://ideone.com/yApYp</a></em>)</h3> <p>Only using loops and <code>std::string</code> interface (well, and <code>iostreams</code> for displaying test output) :)</p> <pre><code>#include &lt;iostream&gt; #include &lt;string&gt; typedef std::string::const_iterator It; /* * Extract sequences of non-wildcard characters from pattern range */ std::string extract_token(It &amp;s, It e) // [s,e) is (sub)pattern { It wcard; for (wcard=s; wcard!=e; ++wcard) if ('?' == *wcard) break; std::string token(s,wcard); for (s=wcard; s!=e; ++s) if ('?' != *s) break; // treat '??' as '?' in pattern return token; } /* * Match a (sub)pattern against a (sub)input * * (See "Strategy" above) */ bool match(It patb, It pate, const std::string&amp; input) { while (patb != pate) { // get next token from pattern, advancing patb std::string token = extract_token(patb, pate); // updates patb if (!token.empty()) // could happen if pattern begins/ends with redundant '?' { size_t submatch = input.find(token); // first submatch please while (std::string::npos != submatch) // while we have a submatch { if (match(patb, pate, input.substr(token.size()))) return true; // match completed successfully // look for later potential submatches (*backtrack*) submatch = input.find(token, submatch+1); } return false; // required token not found } } return true; // no (remaining) pattern, always match } bool match(const std::string&amp; pattern, const std::string&amp; input) { // just relay to overload more suited for recursion return match(pattern.begin(), pattern.end(), input); } ////////////////////// // TEST PROGRAM void test(const std::string&amp; pattern, const std::string&amp; input) { std::cout &lt;&lt; std::boolalpha; std::cout &lt;&lt; "match(\"" &lt;&lt; pattern &lt;&lt; "\", \"" &lt;&lt; input &lt;&lt; "\") =&gt; " &lt;&lt; match(pattern, input) &lt;&lt; std::endl; } int main() { // matches test("?????", ""); test("?????", "?????"); test("", ""); test("", "glorious"); test("?r?o", "glorious"); test("some?words?exist", "some silly words should, most definitely, be existing"); test("some??words?exist?", "some silly words should, most definitely, be existing"); // failing matches test("_", ""); test("_", "glorious"); test("_", "glorious"); test("glorious", "glo?ious"); test("?some??words?exist?", "bogus"); } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POSimple wildcard search algorithm in C++
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USsehe
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for your help, but i think @keith.layne is right on this. There are lots of things I didn't understand in that code.
      singulars
      1. PO
      1. UShevele
    2. CO@keith.layne derp! I'm missing a point somewhere. Using the standard algorithms was 'out' (see OP). However, using string::find surely wasn't? Oh, and backtracking is inevitable due to the nature of the patterns. If you don't want to use recursion you _require_ a stack (e.g. as an array...) and that was also specifically 'out' (see OP)
      singulars
      1. PO
      1. USsehe
    3. CO@sehe "Clearly, the explanation itself is worth something." I agree. I was originally commenting tongue-in-cheek and I thought you were being pedantic. Disregard my comments please.
      singulars
      1. PO
      1. USKeith Layne
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload