title: Efficient substring matching in perl
body: <p>I am looking for an efficient solution to do find the longest possible substring in a string tolerating <em>n</em> mismatches in the main string </p>
  
  <p>Eg:
  Main String</p>
  
  <ol>
  <li>AGACGTAC<b>TACTCTACT</b>AGATGCA*TACTCTAC*</li>
  <li>AGACGTAC<b>TACTCTACT</b>AGATGCA*TACTCTAC*</li>
  <li>AGACGTAC<b>TACTCTACA</b>AGATGCA*TACTCTAC*</li>
  <li>AGACGTAC<b>TACTTTACA</b>AGATGCA*TACTCTAC*</li>
  </ol>
  
  <p>Search String:</p>
  
  <ol>
  <li>TACTCTACT  : this should be considered a match to all of the above main strings.</li>
  </ol>
  
  <p>Also I there could be the case where part of the substring is at the end of main string and I would like to pick that up also.</p>
  
  <p>I would appreciate if you could give some pointers.</p>
  
  <p>PS: I will have one search string and about 100  million main strings to search the substring for.</p>
  
  <p>Thanks!
  -Abhi</p>