数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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'。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数lng_i()。它将接收suff、lng、i作为参数。
- d := 一个包含(suff, lng)的新元组。
- lo := 0
- hi := 0
- 对于d中的每个元组(suf, lng)，执行以下操作：
- 如果lng与null相同，则
- lng := 0
- hi := hi + suf的大小 - lng
- 如果hi - 1与i相同，则
- 返回suf
- 否则，如果hi - 1 > i，则
- 对于从lng到suf大小的列表中的值中的索引p和项目q，执行以下操作：
- 如果lo + p与i相同，则
- 返回suf[从索引0到j+1]
- 如果lo + p与i相同，则
- 对于从lng到suf大小的列表中的值中的索引p和项目q，执行以下操作：
- lo := hi
- 如果lng与null相同，则
- 返回False
- 定义一个函数hlp_ii()。它将接收str1、str2作为参数。
- ub := str1的大小和str2的大小中的最小值。
- cnt := 0
- 对于范围0到ub中的i，执行以下操作：
- 如果str1[i]与str2[i]相同，则
- cnt := cnt + 1
- 否则，
- 返回cnt
- 返回cnt
- 如果str1[i]与str2[i]相同，则
- t_dict := 一个新的映射。
- suff := 一个新的列表。
- lng := 一个新的列表。
- 对于字符串中的每个str，执行以下操作：
对于范围0到str的大小的i，执行以下操作：
- value := str[从索引i到结尾]
- 如果t_dict中不存在value，则
- t_dict[value] := 1
- 在suff的末尾插入value
- 对列表suff进行排序
- suff_len := suff的大小
- 对于范围0到suff_len大小的i，执行以下操作：
- 如果i与0相同，则
- 在lng的末尾插入null
- 否则，
- 在lng的末尾插入hlp_ii(suff[i-1]，suff[i])
- 如果i与0相同，则
- res := 一个新的列表。
- 对于q_list中的每个q，执行以下操作：
- 在res的末尾插入(lng_i(suff, lng, q-1))
- 返回res
示例
让我们看看以下实现，以便更好地理解：
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']
更新于：2021年10月11日
141 次浏览
广告