#include <iostream>
#include <cstring>
using namespace std;
//shortest common supersequence between 2 strings = l1 + l2 - LCS
int mem[20][20];
int max(int a, int b) { return a>b?a:b; }
int scs(char s1[], int l1, char s2[], int l2)
{
for(int i=0; i<l1; i++)
{
for(int j=0; j<l2; j++)
{
if(s1[i] == s2[j])
{
mem[i][j] = (j==0)?1:1 + mem[i][j-1];
}
else
{
mem[i][j] = max((j>0)?mem[i][j-1]:0, (i>0)?mem[i-1][j]:0);
}
}
}
return l1+l2-mem[l1-1][l2-1];
}
int main() {
// your code goes here
memset(mem, -1, sizeof(mem));
char a[] = "subsequence";
char b[] = "queue";
int len = scs(a,strlen(a), b, strlen(b));
cout << "Length of shortest common supersequence between " << a << " and " << b << " is=" << len;
return 0;
}
Output:
Length of shortest common supersequence between subsequence and queue is=12
