title: Checking fuzzy/approximate substring existing in a longer string, in Python?
body: <p>Using algorithms like leveinstein ( leveinstein or difflib) , it is easy to find approximate matches.eg.</p>
  
  <pre><code>&gt;&gt;&gt; import difflib
  &gt;&gt;&gt; difflib.SequenceMatcher(None,"amazing","amaging").ratio()
  0.8571428571428571
  </code></pre>
  
  <p>The fuzzy matches can be detected by deciding a threshold as needed.</p>
  
  <p>Current requirement : To find fuzzy substring based on a threshold in a bigger string.</p>
  
  <p>eg. </p>
  
  <pre><code>large_string = "thelargemanhatanproject is a great project in themanhattincity"
  query_string = "manhattan"
  #result = "manhatan","manhattin" and their indexes in large_string
  </code></pre>
  
  <p>One brute force solution is to generate all substrings of length N-1 to N+1 ( or other matching length),where N is length of query_string, and use levenstein on them one by one and see the threshold.</p>
  
  <p>Is there better solution available in python , preferably an included module in python 2.7 , or an externally available module .</p>
  
  <p><strong>---------------------UPDATE AND SOLUTION ----------------</strong></p>
  
  <p>Python regex module works pretty well, though it is little bit slower than inbuilt <code>re</code> module for fuzzy substring cases, which is an obvious outcome due to extra operations.
  The desired output is good and the control over magnitude of fuzziness can be easily defined.</p>
  
  <pre><code>&gt;&gt;&gt; import regex
  &gt;&gt;&gt; input = "Monalisa was painted by Leonrdo da Vinchi"
  &gt;&gt;&gt; regex.search(r'\b(leonardo){e&lt;3}\s+(da)\s+(vinci){e&lt;2}\b',input,flags=regex.IGNORECASE)
  &lt;regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)&gt;
  </code></pre>