Problem:

Shortest Common Non-Subsequence

A subsequence of a sequence $P$ is a sequence that can be derived from the original sequence $P$ by picking up some or no elements of $P$ preserving the order. For example, "ICPC" is a subsequence of "MICROPROCESSOR".

  A common subsequence of two sequences is a subsequence of both sequences. The famous longest common subsequence problem is finding the longest of common subsequences of two given sequences.

  In this problem, conversely, we consider the shortest common non-subsequence problem: Given two sequences consisting of 0 and 1, your task is to find the shortest sequence also consisting of 0 and 1 that is a subsequence of neither of the two sequences.

Input

  The input consists of a single test case with two lines. Both lines are sequences consisting only of 0 and 1. Their lengths are between 1 and 4000, inclusive.

Output

  Output in one line the shortest common non-subsequence of two given sequences. If there are two or more such sequences, you should output the lexicographically smallest one. Here, a sequence $P$ is lexicographically smaller than another sequence $Q$ of the same length if there exists $k$ such that $P_1 = Q_1, ... , P_{k-1} = Q_{k-1}$, and $P_k < Q_k$, where $S_i$ is the $i$-th character of a sequence $S$.

			

Sample Input 1

0101
1100001

Sample Output 1

0010

Sample Input 2

101010101
010101010

Sample Output 2

000000

Sample Input 3

11111111
00000000

Sample Output 3

01



Sample input:
0101
1100001


Sample output:
0010

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
import os
import sys


def main():
    S = inp()
    T = inp()
    print(solve(S, T))


def solve(S, T):
    sn = len(S)
    tn = len(T)

    sd = [[sn + 1] * (sn + 1), [sn + 1] * (sn + 1)]
    for i in range(sn):
        idx = ord(S[i]) - ord('0')
        for j in range(i, -1, -1):
            if sd[idx][j] != sn + 1:
                break
            sd[idx][j] = i + 1
    td = [[tn + 1] * (tn + 1), [tn + 1] * (tn + 1)]
    for i in range(tn):
        idx = ord(T[i]) - ord('0')
        for j in range(i, -1, -1):
            if td[idx][j] != tn + 1:
                break
            td[idx][j] = i + 1
    #dprint('sd', sd)
    #dprint('td', td)

    sb = [[[] for _ in range(sn + 2)] for _ in range(2)]
    for b in (0, 1):
        for i in range(sn + 1):
            sb[b][sd[b][i]].append(i)
        sb[b][sn + 1].append(sn + 1)
    tb = [[[] for _ in range(tn + 2)] for _ in range(2)]
    for b in (0, 1):
        for i in range(tn + 1):
            tb[b][td[b][i]].append(i)
        tb[b][tn + 1].append(tn + 1)
    #dprint('sb', sb)
    #dprint('tb', tb)

    INF = max(sn, tn) + 2
    arr_temp = [INF] * (tn + 2)
    dists = [array.array('i', arr_temp) for _ in range(sn + 2)]
    q = set()
    q.add((sn + 1, tn + 1))
    d = 0
    while q:
        nq = set()
        for i, j in q:
            if dists[i][j] != INF:
                continue
            dists[i][j] = d
            for b in (0, 1):
                for ni in sb[b][i]:
                    for nj in tb[b][j]:
                        if dists[ni][nj] == INF and (ni, nj) not in q:
                            nq.add((ni, nj))
        d += 1
        q = nq

    #dprint('dists', dists)

    ans = []
    i, j = 0, 0
    d = dists[0][0]
    while (i, j) != (sn + 1, tn + 1):
        #dprint('->', i, j)
        ni = sd[0][i] if i < sn + 1 else sn + 1
        nj = td[0][j] if j < tn + 1 else tn + 1
        if dists[ni][nj] == d - 1:
            ans.append('0')
        else:
            ans.append('1')
            ni = sd[1][i] if i < sn + 1 else sn + 1
            nj = td[1][j] if j < tn + 1 else tn + 1
        i = ni
        j = nj
        d -= 1

    return ''.join(ans)


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    p=input()
    q=input()
    lp=len(p)
    lq=len(q)
    memop=[[0,0] for _ in [0]*(lp+2)]
    memoq=[[0,0] for _ in [0]*(lq+2)]
    memop[lp+1]=[lp+1,lp+1]
    memoq[lq+1]=[lq+1,lq+1]
    memop[lp]=[lp+1,lp+1]
    memoq[lq]=[lq+1,lq+1]
    
    for i in range(lp-1,-1,-1):
        if p[i]=="0":
            memop[i][0]=i+1
            memop[i][1]=memop[i+1][1]
        else:
            memop[i][0]=memop[i+1][0]
            memop[i][1]=i+1
    for i in range(lq-1,-1,-1):
        if q[i]=="0":
            memoq[i][0]=i+1
            memoq[i][1]=memoq[i+1][1]
        else:
            memoq[i][0]=memoq[i+1][0]
            memoq[i][1]=i+1
    
    dp=[dict() for _ in [0]*(lp+2)]
    dp[lp+1][lq+1]=[0,0]
    q=[[0,0]]
    while q:
        i,j=q.pop()
        if j not in dp[i].keys():
            dp[i][j]=[None,None]
            a,b=None,None
        else:
            a,b=dp[i][j]
        if a==None or b==None:
            q.append([i,j])
            if a==None:
                ap,bq=memop[i][0],memoq[j][0]
                if bq not in dp[ap].keys():
                    dp[ap][bq]=[None,None]
                    q.append([ap,bq])
                else:
                    aa,bb=dp[ap][bq]
                    if aa==None or bb==None:
                        q.append([ap,bq])
                    else:
                        dp[i][j][0]=min(aa,bb)+1
            if b==None:
                ap,bq=memop[i][1],memoq[j][1]
                if bq not in dp[ap].keys():
                    dp[ap][bq]=[None,None]
                    q.append([ap,bq])
                else:
                    aa,bb=dp[ap][bq]
                    if aa==None or bb==None:
                        q.append([ap,bq])
                    else:
                        dp[i][j][1]=min(aa,bb)+1

    q=[[0,0]]
    ans=""
    while q:
        i,j=q.pop()
        a,b=dp[i][j]
        if a==0 or b==0:
            break
        if a>b:
            q.append([memop[i][1],memoq[j][1]])
            ans+="1"
        else:
            q.append([memop[i][0],memoq[j][0]])
            ans+="0"
    print(ans)
                
if __name__=='__main__':
    main()