• + 0 comments

    The following codes work by pypy 3

    na=len(a)
    nb=len(b)
    dp=[[0]*(nb+1) for _ in range(na+1)]
    for i in range(na):
        for j in range(nb):
            if a[i]==b[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
    
    suff=[[0]*(nb+1) for _ in range(na+1)]
    for i in range(na-1,-1,-1):
        for j in range(nb-1,-1,-1):
            if a[i]==b[j]:
                suff[i][j]=suff[i+1][j+1]+1
            else:
                suff[i][j]=max(suff[i+1][j],suff[i][j+1])
    
    cur = dp[na][nb]      
    ret = 0
    for i in range(na+1):
        used=[False]*(256)
    
        for j in range(nb):
            if used[ord(b[j])]==True:
                continue
            now=dp[i][j]+ suff[i][j+1] + 1
            if now == cur+1:
                used[ord(b[j])]=True
                ret+=1
    return ret