title: Longest Common Substring with wrong character tolerance
body: <p>I have a script I found on here that works well when looking for the Lowest Common Substring.</p>
  
  <p>However, I need it to tolerate some incorrect/missing characters. I would like be able to either input a percentage of similarity required, or perhaps specify the number of missing/wrong characters allowable.</p>
  
  <p>For example, I want to find this string:</p>
  
  <p><strong>big yellow school bus</strong></p>
  
  <p>inside of this string:</p>
  
  <p><strong>they rode the bigyellow schook bus that afternoon</strong></p>
  
  <p>This is the code i'm currently using:</p>
  
  <pre><code>function longest_common_substring($words) {
      $words = array_map('strtolower', array_map('trim', $words));
      $sort_by_strlen = create_function('$a, $b', 'if (strlen($a) == strlen($b)) { return strcmp($a, $b); } return (strlen($a) &lt; strlen($b)) ? -1 : 1;');
      usort($words, $sort_by_strlen);
  
      // We have to assume that each string has something in common with the first
      // string (post sort), we just need to figure out what the longest common
      // string is. If any string DOES NOT have something in common with the first
      // string, return false.
      $longest_common_substring = array();
      $shortest_string = str_split(array_shift($words));
  
      while (sizeof($shortest_string)) {
          array_unshift($longest_common_substring, '');
          foreach ($shortest_string as $ci =&gt; $char) {
              foreach ($words as $wi =&gt; $word) {
                  if (!strstr($word, $longest_common_substring[0] . $char)) {
                      // No match
                      break 2;
                  }
              }
              // we found the current char in each word, so add it to the first longest_common_substring element,
              // then start checking again using the next char as well
              $longest_common_substring[0].= $char;
          }
          // We've finished looping through the entire shortest_string.
          // Remove the first char and start all over. Do this until there are no more
          // chars to search on.
          array_shift($shortest_string);
      }
  
      // If we made it here then we've run through everything
      usort($longest_common_substring, $sort_by_strlen);
  
      return array_pop($longest_common_substring);
  }
  </code></pre>
  
  <p>Any help is much appreciated.</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>The PHP levenshtein function is limited to 255 characters, and some of the haystacks i'm searching are 1000+ characters.</p>