在python中所有可能的子串集合中找出给定位置给定字符串的子串的程序

Z时代
2024-01-10
分类：综合

假设我们提供了 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]))