Реалізація алгоритму

# Введемо послідовності

s = input('Введіть першу послідовність')

t = input('Введіть другу послідовність')

# Задамо величину штрафу

g = -2

# Задамо мінімально допустиме число

MINIMUM = -1000000

# Проініціалізуємо 3 вагові матриці та матриці шляхів

a = []

b = []

c = []

wayA = []

wayB = []

wayC = []

for x inrange(len(s)):

lineA = []

lineB = []

lineC = []

lineWayA = []

lineWayB = []

lineWayC = []

for y in range(len(t)):

lineA.append(0)

lineB.append(0)

lineC.append(0)

lineWayA.append([])

lineWayB.append([])

lineWayC.append([])

a.append(lineA)

b.append(lineB)

c.append(lineC)

wayA.append(lineWayA)

wayB.append(lineWayB)

wayC.append(lineWayC)

# Проставимо початкові штрафи у вагових матрицях

for x inrange(s):

a[x][0] = x * g

b[x][0] = x * g

c[x][0] = x * g

for y inrange(t):

a[y][0] = y * g

b[y][0] = y * g

c[y][0] = y * g

# Почнемо заповнювати вагові матриці значеннями за рекурентними формулами:

# Матрицю a заповнюємо за правилом:

# a[x][y] = p[x][y] + max(a[x-1][y-1], b[x-1][y-1],c[x-1][y-1])

# p = 1, якщо s[x] == t[y], інакше p=-1

# Матрицю b заповнюємо за правилом:

# b[x][y] = max(a[x][y-k]-k*g, c[x][y-k]-k*g), 1<=k<=y

# Матрицю c заповнюємо за правилом:

# c[x][y] = max(a[x-k][y]-k*g, c[x-k][y]-k*g), 1<=k<=x

# Шлях будемо запом'ятовувати таким чином: [matrix,x,y]

for x inrange(1, len(s)):

for y inrange(1, len(t)):

# Розрахуємо елемент мариці a

a[x][y] = max(a[x-1][y-1],b[x-1][y-1],c[x-1][y-1])

if (a[x][y] == a[x-1][y-1]):

wayA[x][y].append('a')

if (a[x][y] == b[x-1][y-1]):

wayA[x][y].append('b')

if (a[x][y] == c[x-1][y-1]):

wayA[x][y].append('c')

wayA[x][y].append(x - 1)

wayA[x][y].append(y - 1)

if s[x] == t[y]:

p = 1

else:

p = -1

a[x][y] = a[x][y] + p

# Розрахуємо елемент мариці b

max = MINIMUM

for k inrange(1,y+1):

if (a[x][y - k] - k*g > max):

max = a[x][y - k]

maxX = x

maxY = y - k

maxMatrix = 'a'

if (c[x][y - k] - k*g > max):

max = c[x][y - k]

maxX = x

maxY = y - k

maxMatrix = 'c'

b[x][y] = max

wayB[x][y].append(maxMatrix)

wayB[x][y].append(maxX)

wayB[x][y].append(maxY)

# Розрахуємо елемент мариці c

max = MINIMUM

for k inrange(1,y+1):

if (a[x - k][y] - k*g > max):

max = a[x - k][y]

maxX = x - k

maxY = y

maxMatrix = 'a'

if (b[x - k][y] - k*g > max):

max = b[x - k][y]

maxX = x - k

maxY = y

maxMatrix = 'b'

c[x][y] = max

wayC[x][y].append(maxMatrix)

wayC[x][y].append(maxX)

wayC[x][y].append(maxY)

# Знайдемо максимальний крайній елемент з трьох матриць:

x = len(s)

y = len(t)

if (a[x][y] >= b[x][y]) and (a[x][y] >= c[x][y]):

matrix = 'a'

if (b[x][y] >= a[x][y]) and (b[x][y] >= c[x][y]):

matrix = 'b'

if (c[x][y] >= a[x][y]) and (c[x][y] >= b[x][y]):

matrix = 'c'

# Починаємо зворотній хід і заповнюємо результуючи матриці:

result1 = ''

result2 = ''

while (x > 0) and (y > 0):

if matrix == 'a':

result1 = s[x] + result1

result2 = t[y] + result2

parentMatrix = wayA[x][y][0]

parentX = wayA[x][y][1]

parentY = wayA[x][y][2]

if matrix == 'b':

result1 = ' ' + result1

result2 = t[y] + result2

parentMatrix = wayB[x][y][0]

parentX = wayB[x][y][1]

parentY = wayB[x][y][2]

if matrix == 'c':

result1 = s[x] + result1

result2 = ' ' + result2

parentMatrix = wayC[x][y][0]

parentX = wayC[x][y][1]

parentY = wayC[x][y][2]

matrix = parentMatrix

x = parentX

y = parentY

# Роздрукуємо вирівняні послідовності

print('Перша послідовність: ' + result1)

print('Друга послідовність: ' + result2)