Problem p03165 (python)

Fixed submission:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    maxpos = (0, 0)
    maxv = dp[0][0]
    for i, j in product(range(S), range(T)):
        if maxv < dp[i+1][j+1]:
            maxpos = (i, j)
            maxv = dp[i+1][j+1]
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if dp[i+1][j+1] == dp[i+1][j]:
            j -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i -= 1
        else:
            x.append(s[i])
            i -= 1
            j -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Buggy submission (verdict: Runtime Error):
from itertools import product


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    if i < 0 or j < 0:
        return list()
    if s[i] == t[j]:
        x = dfs(s, t, i-1, j-1, dp)
        return x + [i]
    else:
        x = dfs(s, t, i-1, j, dp)
        y = dfs(s, t, i, j-1, dp)
        return x if len(x) > len(y) else y


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    x = dfs(s, t, i, j, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Buggy submission (verdict: Runtime Error):
from itertools import product
from collections import deque


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    if i < 0 or j < 0:
        return list()
    if s[i] == t[j]:
        x = dfs(s, t, i-1, j-1, dp)
        return x + [i]
    else:
        x = dfs(s, t, i-1, j, dp)
        y = dfs(s, t, i, j-1, dp)
        return x if len(x) > len(y) else y


def solve(s, t):
    maxpos, dp = lcs(s, t)
    x = dfs(s, t, *maxpos, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))