在python中所有可能的子串集合中找出给定位置给定字符串的子串的程序
假设我们提供了n个字符串；str1,str2,str3,.....,strn.现在，让我们假设substri是一个包含stri的所有子串的集合。所有substr集合的并集是substr_union。我们现在有q个查询，我们必须找到集合substr_union的第q个元素。集合substr_union按字典顺序排序，索引从1开始。
因此，如果输入类似于字符串列表是=['pqr','pqt']，查询是=[4,7,9]，那么输出将是['pqt','qt','t']
第一个字符串的子串是subs_str_1={p,pq,pqr,q,qr,r},sub_str_2={p,pq,pqt,q,qt,t}。
这两个集合的并集或substr_union是{p,pq,pqr,pqt,q,qr,qt,r,t}。
所以索引4、7和9处的项目分别是'pqt'、qt'和't'。
示例
让我们看看以下实现以获得更好的理解-
def lng_i(suff, lng, i):
d = zip(suff,lng)
lo = hi = 0
for suf, lng in d:
if lng is None:
lng = 0
hi += len(suf) - lng
if hi - 1 == i:
return suf
elif hi - 1 > i:
for p, q in enumerate(list(range(lng, len(suf)))):
if lo + p == i:
return suf[:q+1]
lo = hi
return False
def hlp_ii(str1,str2):
ub = min(len(str1), len(str2))
cnt = 0
for i in range(ub):
if str1[i] == str2[i]:
cnt += 1
else:
return cnt
return cnt
def solve(strings,q_list):
t_dict = {}
suff = []
lng = []
for str in strings:
for i in range(len(str)):
value = str[i:]
if value not in t_dict:
t_dict[value] = 1
suff.append(value)
suff.sort()
suff_len = len(suff)
for i in range(suff_len):
if i == 0:
lng.append(None)
else:
lng.append(hlp_ii(suff[i-1], suff[i]))
res = []
for q in q_list:
(res.append(lng_i(suff, lng, q-1)))
return res
print(solve(['pqr', 'pqt'], [4, 7, 9]))输入
['pqr', 'pqt'], [4, 7, 9]输出结果
['pqt', 'qt', 't']