title: String similarity: how exactly does Bitap work?
body: <p>I'm trying to wrap my head around the <a href="http://en.wikipedia.org/wiki/Bitap_algorithm" rel="noreferrer">Bitap</a> algorithm, but am having trouble understanding the reasons behind the steps of the algorithm.</p>
  
  <p>I understand the basic premise of the algorithm, which is (correct me if i'm wrong):</p>
  
  <pre><code>Two strings:     PATTERN (the desired string)
                   TEXT (the String to be perused for the presence of PATTERN)
  
  Two indices:     i (currently processing index in PATTERN), 1 &lt;= i &lt; PATTERN.SIZE
                   j (arbitrary index in TEXT)
  
  Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) &amp;&amp; PATTERN[i] == TEXT[j], S(0) = 1
  </code></pre>
  
  <p>In english terms, <code>PATTERN.substring(0,i)</code>  matches a substring of TEXT if the previous substring <code>PATTERN.substring(0, i-1)</code> was successfully matched and the character at <code>PATTERN[i]</code> is the same as the character at <code>TEXT[j]</code>.</p>
  
  <p>What I don't understand is the bit-shifting implementation of this. <a href="http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f08/Artikler/09/Baeza92.pdf" rel="noreferrer">The official paper detailing this algorithm basically lays it out</a>, but I can't seem to visualize what's supposed to go on.  <strong>The algorithm specification is only the first 2 pages of the paper</strong>, but I'll highlight the important parts:</p>
  
  <p>Here is the bit-shifting version of the concept:</p>
  
  <p><img src="https://i.stack.imgur.com/c9gWw.png" alt="enter image description here"></p>
  
  <p>Here is T[text] for a sample search string:</p>
  
  <p><img src="https://i.stack.imgur.com/dyCmx.png" alt="enter image description here"></p>
  
  <p>And here is a trace of the algorithm. </p>
  
  <p><img src="https://i.stack.imgur.com/ZFfHi.png" alt="enter image description here"></p>
  
  <p>Specifically, I don't understand what the T table signifies, and the reason behind <code>OR</code>ing an entry in it with the current state.</p>
  
  <p>I'd be grateful if anyone can help me understand what exactly is going on</p>