Computer Science

categories: computer science

Hello everyone,
Below you will find a video with a detailed explanation of the algorithm for determining the length of the longest common subsequence (improved algorithm). Its operation, time complexity, and usefulness. Below you will also find ready-to-use code that you can copy if needed.

I would also like to point out that this material is the last one in the algorithms sub-course of the IT matura course. If you've finished it, congratulations! I now invite you to check out the next sub-course, this time on databases :)
Code:

slowo1 = "alamakota"  # will be the row
slowo2 = "ala"        # will be the column
dlugoscSlowo1 = len(slowo1)
dlugoscSlowo2 = len(slowo2)
tablica = []

for i in range(dlugoscSlowo1 + 1):  # column
    tablica.append([0] * (dlugoscSlowo2 + 1))  # row

for i in range(dlugoscSlowo1 + 1):
    tablica[i][0] = 0  # i is the column

for i in range(dlugoscSlowo2 + 1):
    tablica[0][i] = 0  # i is the row

for i in range(1, dlugoscSlowo2 + 1):
    for j in range(1, dlugoscSlowo1 + 1):
        if slowo2[i - 1] == slowo1[j - 1]:
            tablica[j][i] = tablica[j - 1][i - 1] + 1
        else:
            tablica[j][i] = max(tablica[j - 1][i], tablica[j][i - 1])

for i in range(dlugoscSlowo2 + 1):
    for j in range(dlugoscSlowo1 + 1):
        print(str(tablica[j][i]) + " ", end="")
    print()

"""
for i in range(dlugoscSlowo2 + 1):
    for j in range(dlugoscSlowo1 + 1):
        tablica[j][i] = 0
"""
                  

Video:

Thank you for reading!

---

The End