Algorithm:
1) Make a matrix m x n where m = string1 length and n = string2 length
2) if str1[i] != str2[j] then put matrix element as 0
3) if str1[i] == str2[j] then put matrix element as 1 + previous diagonal element. set max
4) form the longest substring by examining max element in matrix and going back diagonally to collect previous characters
$str1 = "GeeksForGeeks";
$str2 = "AllGeeksQuiz";
$len1 = strlen($str1);
$len2 = strlen($str2);
$matrix = array();
$max = 0;
for ($i = 0; $i < $len1 ; $i++) {
for ($j = 0; $j < $len2 ; $j++) {
if ($str1[$i] == $str2[$j]) {
if (($i == 0) || ($j == 0))
$matrix[$i][$j] = 1;
else
$matrix[$i][$j] = $matrix[$i-1][$j-1] + 1;
if ($matrix[$i][$j] > $max) {
$maxI = $i;
$maxJ = $j;
$max = $matrix[$i][$j];
}
}
}
}
if ($max > 0) {
$substring = '';
for ($k = 0; $k < $max ; $k++) {
$substring = $str1[$maxI-$k] . $substring;
}
echo "Longest Substring: $substring\n";
} else {
echo "No substring\n";
}