Problem p03165 (python)

Fixed submission:
import sys
sys.setrecursionlimit(3003)
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    dp = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    for i in range(N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    print(get(s, t, N, M, dp))

def get(s, t, i, j, dp):
    if i == 0 or j == 0:
        return ""

    if s[i]==t[j]:
        return get(s, t, i-1, j-1, dp) + s[i]
    elif s[i] != t[j]:
        if dp[i-1][j] > dp[i][j-1]:
            return get(s, t, i-1, j, dp)
        else:
            return get(s, t, i, j-1, dp)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
    string S,T;
    cin>>S>>T;
    int N = S.length();
    int M = T.length();
    vector<vector<int>> dp(N+1, vector<int>(M+1,0));
    vector<vector<pair<int,int>>> prev(N+1, vector<pair<int,int>>(M+1, pair(-1,-1)));
    for(int i = 1;i < N+1;i++){
        for(int j = 1;j < M+1;j++){
            if(S[i-1] != T[j-1] || dp[i][j-1] != dp[i-1][j-1] || dp[i-1][j] != dp[i-1][j-1]){
                if(dp[i][j-1] > dp[i-1][j]){
                    dp[i][j] = dp[i][j-1];
                    prev[i][j] = pair(i,j-1);
                }else{
                    dp[i][j] = dp[i-1][j];
                    prev[i][j] = pair(i-1,j);
                }
            }else{
                dp[i][j] = dp[i-1][j-1]+1;
                prev[i][j] = pair(-2,-2);
            }
        }
    }

    pair<int,int> to = pair(N,M);
    string res = "";
    while(to != pair(-1,-1)){
        pair<int,int> p = prev[to.first][to.second];
        if(p == pair(-2,-2)){
            res += S[to.first-1];
            to = pair(to.first-1, to.second-1);
        }else{
            to = p;
        }
    }
    reverse(res.begin(),res.end());
    cout<<res<<endl;
}

Buggy submission (verdict: Runtime Error):
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    # last_letter[i][j] := s_i, t_jまでを使ったLCSの最後の文字
    dp = [[-1]*(M+1) for i in range(N+1)]
    last_letter = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    last_letter[0] = ['' for n in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
        last_letter[i][0] = ''
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
                last_letter[i][j] = s[i]
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                    last_letter[i][j] = last_letter[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                    last_letter[i][j] = last_letter[i][j-1]
    print(get(s, t, N, M, dp, last_letter))

def get(s, t, i, j, dp, last_letter):
    if i == 0 or j == 0:
        return ""
    ll = last_letter[i][j]
    if s[i]==t[j]==ll:
        return get(s, t, i-1, j-1, dp, last_letter) + s[i]
    elif ll == s[i] and ll != t[j]:
        return get(s, t, i, j-1, dp, last_letter)
    elif ll == t[j] and ll != s[i]:
        return get(s, t, i-1, j, dp, last_letter)
    elif ll != t[j] and ll!= s[i]:
        return get(s, t, i-1, j-1, dp, last_letter)

if __name__ == "__main__":
    main()