Python program to implement Longest Common Sub-sequence

# LCS(Longest Common Subsequence)

class lcs:
    val=0
    flag=0
    
Table=[]  # 2D Matrix
row=0
col=0


def getData():
    global row
    global col

    string1Length=int(input("Enter length of first string: "))
    col = string1Length+2

    string2Length=int(input("Enter length of second string: "))
    row = string2Length+2

    # Table=new struct lcs*[row]
    for i in range(row):
        Table.append([])
        for j in range(col):
            Table[i].append(lcs())

            Table[i][j].val = 0
            Table[i][j].flag = 0

    print("\nEnter first string: ")
    for i in range(2, col):
        character=input()
        Table[0][i].val = character    

    print("\nEnter second string: ")
    for i in range(2, row):
        character=input()
        Table[i][0].val = character


def showOutput():
    print("\nCalculation Table:\n")
    for i in range(row):
        for j in range(col):
            if i==0 or j==0:
                character=Table[i][j].val
                print(character,"\t",end="")
            
            else:
                print(Table[i][j].val,"\t",end="")
        print("\n")

    # Calculating the substring
    subStringLength=Table[row-1][col-1].val
    subString=[0] * subStringLength
    j = col-1
    temp=0
    k = subStringLength-1
    for i in range(row-1, 1, -1):
        if j < 2:
            j = temp
        while j > 1:
            if Table[i][j].flag == 1:
                temp = j
                character = Table[i][0].val
                subString[k] = character
                k=k-1
                break
            j=j-1
     
    print("\LCS: ", end="")
    for i in range(subStringLength):
        print("\t",subString[i],end="")
    print("\n")


def maximum(x, y):
    if x >= y:
        return x
    else:
        return y


def tableCalculation():
    for i in range(2, row):
        for j in range(2, col):
            if Table[i][0].val == Table[0][j].val:
                Table[i][j].val = Table[i-1][j].val + 1
                Table[i][j].flag = 1
            
            else:
                temp = maximum(Table[i][j-1].val , Table[i-1][j].val)
                Table[i][j].val = temp
            

# __________________________ Main Block Starts __________________________
print("\t\t\t____Longest Common Subsequence (LCS)____")
getData();
tableCalculation();
showOutput();

Output