Compute Shortest Common Supersequence in Python

Hello guys, now we are going to Compute Shortest Common Supersequence using Python. If you are here, then you are moving in the right direction looking for the solution. let me first explain what is shortest common supersequence.

Finding the shortest string that is common in two different strings is known as the shortest supersequence. so using Python now we are going to find it. Here we are going to lists and its operations and nested loops.

Lists and its operations:

Now we are going to learn 3 operations of lists which are being used for this problem.

1. Append:

a=[]
a.append(4)
print(a)
     output:
[4]

Here we have created a list a and we used append operation to add 4 into the list.

2. Extend:

a=[4]
b=[5]
a.extend(b)
print(a)
      output:
[4, 5]

Here we have created two lists with elements in it and used to extend operation to add elements of one list to the other.

3. Remove:

a=[4,5]
a.remove(a[0])
print(a)
   output:
[5]

Here we have created a list with two or more than elements in it and used remove operation to remove an element in it.

How to compute Shortest Common Supersequence in Python

Now here is the code for the above problem.

a=input("Enter the string 1 :")
b=input("Enter the string 2: ")
c=[]
d=[]
e=[]
for i in a:
    c.append(i)
for i in b:
    d.append(i)
e.append(c[0])
p=1
q=0
if c[0]==d[0]:
    d.remove(d[0])
else:
    while (p+1)<=len(c):
        while (q+1)<=len(d):
            if c[p]==d[q]:
                while q!=0:
                    e.append(d[0])
                    d.remove(d[0])
                    q-=1
                e.append(c[p])
                d.remove(d[q])
                p+=1
                q=0
                if (p+1)>len(c) and len(d)>0:
                    e.extend(d)
                    d.clear()
            elif c[p]==c[p-1]:
                e.append(c[p])
                p+=1
                q=0
                if (p + 1)>len(c) and len(d)>0:
                    e.extend(d)
                    d.clear()
            elif (q+1)==len(d):
                e.append(c[p])
                p+=1
                q=0
                if (p + 1)>len(c) and len(d)>0:
                    e.extend(d)
                    d.clear()
            else:
                q+=1
print(*e,sep="")

Here we have created many lists and took input from the user and divide that string into characters. Then we add 1st string characters to the newly created list one by one by comparing with the 2nd string characters by following some conditions.

Input:

uday 
vinay

Output:

udvinay

Also read: NumPy np.hermegrid2d() and np.hermegrid3d() methods in Python

Leave a Reply