Compute Shortest Common Supersequence in PHP

Hello Friends, In this tutorial, we will look at how to compute the shortest common supersequence with PHP language. We will use dynamic programming to get the longest common subsequence first and then will look at how to get the shortest common supersequence with the help of the longest common subsequence.

Shortest Common Supersequence

If you do not have an idea of the longest common subsequence than please check this post to know more about such subsequences Longest Common Subsequence using Dynamic Programming. To get the implementation of this in PHP, please refer Code for LCS implemented in PHP.

What is Supersequence?
If we have two strings s1 and s2, then a string s3 will be supersequence if s3 has both s1 and s2 as it’s subsequences. To get the shortest we need to return the one having the shortest length, there may be more than one such strings.

Let’s take s1= “abac” and s2 = “cab” then LCS(longest common subsequence) of these two is “ab” and the supersequence is s3 = “cabac” as s3 has s1 starting from index[1,4] and s2 from index[0,2].

The idea used here is to get the LCS of both the strings first and then we can use characters present in LCS to represent a character for both s1 and s2, all the remaining character has to be put in the s3 according to the order in which they are present in s1 and s2. So, Length of supersequence(s3) will be
( s1.length + s2.length – LCS.length).

We keep two indices i,j both starting from 0 for s1,s2 respectively. We also keep one more index k starting from 0 for LCS.
If s1[i] and s2[j] both matches the LCS[k] we need to consider this character only once in our answer and if neither of s1[i] and s2[j] matches LCS[k] than these two characters is not there in LCS and we need to add both the characters in our answer and if s1[i] matches to LCS[k] and s2[j] does not then we add s2[j] as it is not there in LCS and lastly if s2[j] matches to LCS[k] and s1[i] does not then we add s1[i] as it is not there in LCS.

Look at the implementation :

 <?php  

 $s1="abac";
 $s2="cab";

 $lcs="ab";  //  Use link mentioned above to get lcs of two strings s1 and s2 as parameters.

 $s3="";

 $i=0;
 $j=0;
 $k=0;


while($i < strlen($s1) && $j < strlen($s2))
{
  if( !( $s1[$i] == $lcs[$k] || $s2[$j] == $lcs[$k] ) )
  {
    
    $s3.=$s1[$i];
    $i++;

    $s3.=$s2[$j];
    $j++;
    
  }
  else if($s1[$i]==$lcs[$k] && $s2[$j]==$lcs[$k] )
  {
    $s3.=$lcs[$k];
    $k++;
    $i++;
    $j++;
  }
  else if($s1[$i]!=$lcs[$k] && $s2[$j]==$lcs[$k])
  {
    $s3.=$s1[$i];
    $i++;
  }
  else{
    $s3.=$s2[$j];
    $j++;
  }
}

while($i < strlen($s1)) 
{
  $s3.=$s1[$i];
  $i++;
}

while($j < strlen($s2)) 
{
  $s3.=$s2[$j];
  $j++;
}

echo "Shortest Common Supersequence is \"" . $s3."\"." ; 

?>

 

Output:

Shortest Common Supersequence is "cabac".

Thank You

 

Leave a Reply

Your email address will not be published. Required fields are marked *