DEV Community

Discussion on: PHP Damarau levenstein on Longest Match SubString

Collapse
moay profile image
moay • Edited

So, I played around a bit, sadly didn't have time for deeper look and a lot of tries. Here is my quick solution to this:

public function getLongestMatchingSubstring(string $string1, string $string2): ?string
{
    $shorterString = strlen($string1) > strlen($string2) ? $string1 : $string2;
    $longerString = strlen($string1) > strlen($string2) ? $string2 : $string1;

    $shorterStringLength = strlen($shorterString);
    $longestMatch = null;
    $matchingLength = 1;
    $index = 0;

    do {
        $possibleMatch = substr($shorterString, $index, $matchingLength);
        if (strpos($longerString, $possibleMatch) !== false) {
            $longestMatch = $possibleMatch;
            $matchingLength++;
        } else {
            $index++;
        }
    } while ($shorterStringLength - $index - $matchingLength >= 0);

    return $longestMatch;
}
Enter fullscreen mode Exit fullscreen mode

This seems to outperform the posted solution in most cases (by a huge factor up to 500 or more). For the extreme examples of having one very long string and one very short, both solutions seem to be pretty close, depending on the string order. While the order can easily be fixed, this still is way quicker in most "normal" circumstances.

Let me know if you find even better solutions. :-)