Last active
December 11, 2015 15:29
-
-
Save zxteloiv/4621110 to your computer and use it in GitHub Desktop.
longest common substring in php, note it's different from longest common subsequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/local/php/bin/php | |
<?php | |
function get_longest_common_substring($string_1, $string_2) { | |
$string_1_length = strlen($string_1); | |
$string_2_length = strlen($string_2); | |
$return = ""; | |
if ($string_1_length === 0 || $string_2_length === 0) { | |
// No similarities | |
return $return; | |
} | |
$longest_common_subsequence = array(); | |
// Initialize the CSL array to assume there are no similarities | |
for ($i = 0; $i < $string_1_length; $i++) { | |
$longest_common_subsequence[$i] = array(); | |
for ($j = 0; $j < $string_2_length; $j++) { | |
$longest_common_subsequence[$i][$j] = 0; | |
} | |
} | |
$largest_size = 0; | |
for ($i = 0; $i < $string_1_length; $i++) { | |
for ($j = 0; $j < $string_2_length; $j++) { | |
// Check every combination of characters | |
if ($string_1[$i] === $string_2[$j]) { | |
// These are the same in both strings | |
if ($i === 0 || $j === 0) { | |
// It's the first character, so it's clearly only 1 character long | |
$longest_common_subsequence[$i][$j] = 1; | |
} else { | |
// It's one character longer than the string from the previous character | |
$longest_common_subsequence[$i][$j] = $longest_common_subsequence[$i - 1][$j - 1] + 1; | |
} | |
if ($longest_common_subsequence[$i][$j] > $largest_size) { | |
// Remember this as the largest | |
$largest_size = $longest_common_subsequence[$i][$j]; | |
// Wipe any previous results | |
$return = ""; | |
// And then fall through to remember this new value | |
} | |
if ($longest_common_subsequence[$i][$j] === $largest_size) { | |
// Remember the largest string(s) | |
$return = substr($string_1, $i - $largest_size + 1, $largest_size); | |
} | |
} | |
// Else, $CSL should be set to 0, which it was already initialized to | |
} | |
} | |
// Return the list of matches | |
return $return; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment