StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First piece of advice, take a deep breath. You're clearly stressed, and when you're stressed the first thing that happens is that large chunks of your brain shut down. This makes understanding hard, which increases stress, and you've got a problem.</p> <p>A 5 minute timeout to improve your headspace may seem impossible to take, but can be surprisingly helpful.</p> <p>Now that said, the algorithm is based on a simple principle. Suppose that I'm trying to match a substring of length <code>m</code>. I'm going to first look at character at index <code>m</code>. If that character is not in my string, I know that the substring I want can't start in characters at indices <code>1, 2, ... , m</code>.</p> <p>If that character is in my string, I'll assume that it is at the last place in my string that it can be. I'll then jump back and start trying to match my string from that possible starting place. This piece of information is my first table.</p> <p>Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match <code>anand</code> in <code>ananand</code> successfully match, <code>anan</code>, realize that the following <code>a</code> is not a <code>d</code>, but I've just matched <code>an</code>, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.</p> <p>Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.</p> <p>With this in mind the algorithm works like this:</p> <pre><code>start at beginning of string start at beginning of match while not at the end of the string: if match_position is 0: Jump ahead m characters Look at character, jump back based on table 1 If match the first character: advance match position advance string position else if I match: if I reached the end of the match: FOUND MATCH - return else: advance string position and match position. else: pos1 = table1[ character I failed to match ] pos2 = table2[ how far into the match I am ] if pos1 < pos2: jump back pos1 in string set match position at beginning else: set match position to pos2 FAILED TO MATCH </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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