最大公共子序列（python2）

def subseque(s1, s2):
    res = [['0' for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    m = [[0 for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    # print m
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i + 1][j + 1] = m[i][j] + 1
                res[i + 1][j + 1] = 'xie'
            elif m[i + 1][j] > m[i][j + 1]:
                m[i + 1][j + 1] = m[i + 1][j]
                res[i + 1][j + 1] = 'zuo'
            else:
                m[i + 1][j + 1] = m[i][j + 1]
                res[i + 1][j + 1] = 'shang'
    (i, j) = (len(s1), len(s2))
    print numpy.array(res)
    result = []
    while m[i][j]:
        c = res[i][j]
        if c == 'xie':
            result.append(s1[i - 1])
            i -= 1
            j -= 1
        if c == 'zuo':
            j -= 1
        if c == 'shang':
            i -= 1
    print result

def random_str(randomlength=20):
    str = ''
    chars = 'abcdefghigklmnopqrstuvwxyz'
    length = len(chars) - 1
    random = Random()
    for i in range(randomlength):
        str+=chars[random.randint(0, length)]
    return str