题目A4：字符串的最长公共子序列求解问题
已知两个字符串X和Y，其中X包含m个字符，Y包含n个字符，找出两者之间的最长公共子序列，即在X和Y中从左到右都出现的连续的最长字符串序列。例如，X=“ABCBDAB”，Y=“BCBDDAB”,则X和Y的最长公共子序列即为{“BCBD”}，最长公共子序列可能不唯一。
X = 'ABCBDACB'
Y = 'BCBDCDAB'
judge1 = True
length = 0
max_string = [''] #最后找出来的的字符串的最长公共子序列
temp_string = '' #每一次循环找到的最大长度的字符串
for j in range(len(X)):
for k in range(len(Y)):
if X[j]== Y[k]: #当找到了一个相等的字符之后
temp_string = X[j] #暂存此字符
if j+1<=(len(X)-1) and k+1<=(len(Y)-1): #当此时X的下标j不超过X的长度和Y的下标k不超过Y长度的时
temp1 = j+1 #指向X的下一个字符
temp2 = k+1 #指向Y的下一个字符
judge1 = 1 #判断循环何时结束的标志
while judge1:
if temp1<=(len(X)-1) and temp2<=(len(Y)-1) and X[temp1] == Y[temp2]: #当此时X的下标temp1不超过X的长度和Y的下标temp2不超过Y长度的时,并且此时的字符也相同
temp_string = temp_string+ X[temp1] #将字符补加到temp_string中
temp1 = temp1 + 1 # temp1指向X的下一个字符
temp2 = temp2 + 1 # temp2 指向Y的下一个字符
else: #X[temp1] 与 Y[temp2]不相等之后
if len(temp_string) > len(max_string[0]): #当这次循环找到的最大长度的字符串的长度 > 存储在列表的最长公共子序列 长度
max_string = [] # 清空 最长公共子序列列表
max_string.append(temp_string) # 添加进 最长公共子序列列表
elif len(temp_string) == len(max_string[0]): #当这次循环找到的最大长度的字符串的长度 == 存储在列表的最长公共子序列 长度
if temp_string not in max_string:
max_string.append(temp_string) #将本次找到的最大长度的字符串的长度 也 加入到 最长公共子序列列表
judge1 = False #本次循环结束
print(max_string)
运行结果
