最長共通サブシーケンス-Python-ダイナミックプランニング

import time
import random
import string
import sys
sys.setrecursionlimit(100000)

#     lcs
q= []
def lcs(a, b):
    lena = len(a)
    lenb = len(b)
    c = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
    flag = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
    for i in range(lena):
        for j in range(lenb):
            if a[i] == b[j]:
                c[i + 1][j + 1] = c[i][j] + 1
                flag[i + 1][j + 1] = 'ok'
            elif c[i + 1][j] > c[i][j + 1]:
                c[i + 1][j + 1] = c[i + 1][j]
                flag[i + 1][j + 1] = 'left'
            else:
                c[i + 1][j + 1] = c[i][j + 1]
                flag[i + 1][j + 1] = 'up'
    return c, flag
#  lcs
def printLcs(flag, a, i, j):
    if i == 0 or j == 0:
        return
    if flag[i][j] == 'ok':
        printLcs(flag, a, i - 1, j - 1)
        q.append(a[i - 1])
        print(a[i - 1], end='')
        print(len(q))
    elif flag[i][j] == 'left':
        printLcs(flag, a, i, j - 1)
    else:
        printLcs(flag, a, i - 1, j)

if __name__ == '__main__':
    # a = 'BDCABA'
    # b = 'ABCBDAB'
    s = string.ascii_uppercase  #       (A-Z)
    a=[random.choice(s) for i in range(1000)]
    b=[random.choice(s) for i in range(1000)]
    print(a)
    print(b)
    t1 = time.perf_counter()
    c, flag = lcs(a, b)
    printLcs(flag, a, len(a), len(b))
    t2 =time.perf_counter()
    print()
    print(t2-t1)