给定文本text和待匹配字符串pattern,二者皆只包含小写字母,并且不为空。
在text中找出匹配pattern的最短字符串,匹配指按序包含pattern,但不要求pattern连续。
如text为abaacxbcbbbbacc,pattern为cbc,text中满足条件的是abaacxbcbbbbacc下划线部分。
多行,每行一个text和一个pattern,用空格分隔。
保证1<=|text|,|pattern|<=1000,Σ|text|,Σ|pattern|<=10000。
输出最短匹配序列起止位置(位置下标从0开始),用空格分隔。若有多个答案,输出起止位置最小的答案;若无满足条件的答案,则起止均为-1。
abaacxbcbbbbacc cbc abc x aaabcac ac
4 7 -1 -1 5 6
import sys def func(a, b): temp = {} i = 0 j = 0 start = -1 end = -1 while i < len(a): if a[i] == b[j]: j += 1 if start == -1: start = i end = i else: end = i if j == len(b): if end - start not in temp: temp[end-start] = [start, end] i = start j = 0 start = -1 i += 1 if len(temp) > 0: res = temp[min(temp.keys())] else: res = [-1, -1] res_str = str(res[0]) + " " + str(res[1]) print(res_str) lines = sys.stdin.readlines() for line in lines: text, pattern = line.strip().split() func(text, pattern)