input input lx len ly len MASS ly for in range lx for in range lx for

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
x = input()
y = input()
lx = len(x)
ly = len(y)
MASS= [[0]*(ly + 1) for i in range(lx + 1)]
for i in range(1,lx + 1):
for j in range(1,ly + 1):
if x[i-1] == y[j-1]:
MASS[i][j] = MASS[i-1][j-1] + 1
else:MASS[i][j]= max(MASS[i-1][j],MASS[i][j-1])
HOP = ''
i=lx;j=ly
while i >0 and j >=0:
if x[i-1] == y[j-1]:
HOP +=x[i-1]
i-=1;j-=1
elif MASS[i-1][j] >= MASS[i][j-1] : i -= 1
else: j -= 1
print(HOP)