Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
23
Добавлен:
10.04.2018
Размер:
1.44 Кб
Скачать

s1 = input("First sequence: ")
s2 = input("Second sequence: ")

s1 = "_" + s1
s2 = "_" + s2


p = []
way = []
for i in s1:
stolbik = []
wayStolbik = []
for j in s2:
stolbik.append(0)
wayStolbik.append("")
p.append(stolbik)
way.append(wayStolbik)

for i in range(len(s1)):
p[i][0] = -2 * i

for j in range(len(s2)):
p[0][j] = -2 * j

for x in range(1, len(s1)):
for y in range(1, len(s2)):
left = p[x-1][y] - 2
up = p[x][y-1] - 2

if (s1[x] == s2[y]):
slog = 1
else:
slog = -1

diag = p[x-1][y-1] + slog

p[x][y] = max(left, up, diag)

if (p[x][y] == left):
way[x][y] = "l"
if (p[x][y] == up):
way[x][y] = "u"
if (p[x][y] == diag):
way[x][y] = "d"
res1 = ""
res2 = ""

x = len(s1)-1
y = len(s2)-1

while (way[x][y] != ""):
if (way[x][y] == "d"):
res1 = s1[x] + res1
res2 = s2[y] + res2
x = x - 1
y = y - 1

if (way[x][y] == "u"):
res1 = "_" + res1
res2 = s2[y] + res2
y = y - 1

if (way[x][y] == "l"):
res1 = s1[x] + res1
res2 = "_" + res2
x = x - 1


print("P matrix:")

for s in p:
print(s)

print("Resulting sequence 1: " + res1)
print("Resulting sequence 2: " + res2)



Соседние файлы в папке ФБТ БИ 2курс