题目
子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt是一个子串，而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
输入格式： 输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 10 4 个小写英文字母组成；P 保证是 S 的一个非空子列。
输出格式： 在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
输入样例： atpaaabpabttpcat pat 结尾无空行 输出样例： pabt 结尾无空行
解题思路
P = str(input()) S = str(input()) # P = str("atpaaabpabttpcat") # S = str("pat") def isCunzai(input:str, S:str) -> bool: j = 0 for i in input: if i == S[j]: j += 1 if len(S) == j: return True return False resList = [] PList = list(P) left0 = S[0] right0 = S[-1] left0List = [] right0List = [] for index,val in enumerate(PList): if val == left0: left0List.append(index) if val == right0: right0List.append(index) minLeng = len(P) for i in left0List: for j in right0List: # print(i,j,P[i:j+1]) length = j +1 - i if i<=j and length <= minLeng: PtempStr = (P[i:j+1]) if isCunzai(PtempStr,S) == True: resList.append(PtempStr) minLeng = len(PtempStr) break # print(resList) print(min(resList,key= lambda x:len(x)))
