【备忘】Python取两字符串中的最大相同子串

矩阵取1斜线法

mark_posit_list = []


def get_line(start_x, start_y, matrix_list, string_1):
    # 遍历取1斜线
    if start_x >= len(matrix_list):
        return ''
    elif start_y >= len(matrix_list[start_x]):
        return ''
    elif matrix_list[start_x][start_y] != 1:
        return ''
    mark_posit_list.append((start_x, start_y))
    # print(string_1[start_x], start_x, start_y, matrix_list[start_x][start_y])
    return string_1[start_x] + get_line(start_x + 1, start_y + 1, matrix_list, string_1)


if __name__ == "__main__":
    string_1 = 'abcdef'
    string_2 = 'cbcdefdexgggabcde'
    matrix_list = []
    for idx1, char_1 in enumerate(string_1):
        matrix_list.append([])
        for idx2, char_2 in enumerate(string_2):
            flag = 1 if char_1 == char_2 else 0
            matrix_list[idx1].append(flag)
    print('matrix list')
    for line in matrix_list:
        print(line)
    # 取1斜线
    for x in range(len(string_1)):
        for y in range(len(string_2)):
            if (x, y) in mark_posit_list:
                continue
            line = get_line(x, y, matrix_list, string_1)
            if len(line) <= 4:
                continue
            else:
                print(line)