Problem p03165 (python)

Fixed submission:
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

ans = []
x,y=len(a)-1,len(b)-1
lcs = dp[x][y]
while x > 0 or y > 0:
    if x-1 >= 0 and dp[x-1][y] == lcs:
        x -= 1
    elif y-1 >= 0 and dp[x][y-1] == lcs:
        y -= 1
    else:
        ans.append(a[x])
        y -= 1
        x -= 1
        
        lcs -= 1
print("".join(ans[::-1]))

Buggy submission (verdict: Runtime Error):
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

def findout(x,y):
    stack=[(x,y)]
    while stack:
        x,y=stack.pop()
        if x<0 or y<0:
            continue
        if dp[x][y]==dp[x-1][y-1]+1 and a[x]==b[y]:
            return (x,y)
        stack+=[(x-1,y),(x,y-1)]
        
ans=""
L=dp[-1][-1]
x,y=len(a)-1,len(b)-1
for i in range(L):
    x,y=findout(x,y)
    ans+=a[x]
    x-=1
    y-=1
print(ans[::-1])

Buggy submission (verdict: Runtime Error):
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

Ans=[]
def findout(i,j):
    
    if dp[i][j]==dp[i-1][j-1]+1 and a[i]==b[j]:
        
        return (i-1,j-1)
    temp1=None
    temp2=None
    if i>0:
        temp1=findout(i-1,j)
    if j>0:
        temp2=findout(i,j-1)
    if temp1:
        return temp1
    if temp2:
        return temp2
x,y=len(a)-1,len(b)-1
ans=""
for i in range(dp[-1][-1]):
    x,y=findout(x,y)
    ans+=a[x+1]
print(ans[::-1])

Buggy submission (verdict: Runtime Error):
a=input()
b=input()
dic={}
def findout(i,j):
    if (i,j) in dic:
        return dic[(i,j)]
    
    if i==0 and j==0:
        if a[i]==b[j]:
            return a[i]
        else:
            return ""
    
    elif i==0 and j>0:
        if a[i]==b[j]:
            
            return a[i]
        else:
            
            dic[(i,j)] = findout(i,j-1)
            return dic[(i,j)]
    
    elif i>0 and j==0:
        if a[i]==b[j]:
            return b[j]
        else:
            dic[(i,j)]=findout(i-1,j)
            return dic[(i,j)]
    else:
        if a[i]==b[j]:
            dic[(i,j)]=findout(i-1,j-1)+a[i]
            return dic[(i,j)]
        else:
            temp1=findout(i,j-1)
            temp2=findout(i-1,j)
            if len(temp1)>len(temp2):
                dic[(i,j)]=temp1
            else:
                dic[(i,j)]=temp2
            return dic[(i,j)]
print(findout(len(a)-1,len(b)-1))