title: Approximate substring matching using a Suffix Tree
body: <p>This article discusses approximate substring matching techniques that utilize a <a href="http://en.wikipedia.org/wiki/Suffix_tree" rel="nofollow noreferrer">suffix tree</a> to improve matching time. Each answer addresses a different algorithm.</p>
  
  <ol>
  <li>Approximate substring matching attempts to find a substring (pattern) <em><code>P</code></em> in a string <em><code>T</code></em> allowing up to <em><code>k</code></em> mismatches.</li>
  <li>To learn how to create a suffix tree, click <a href="https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english?lq=1">here</a>. However, some algorithms require additional preprocessing.</li>
  </ol>
  
  <p>I invite people to add new algorithms (even if it's incomplete) and improve answers.</p>