用 Python 编写程序，在一组所有可能的子字符串中找出给定字符串在给定位置的子字符串

pythonserver side programmingprogramming更新于 2025/12/18 18:52:17

假设我们有 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 := hi
- 返回 False
定义一个函数 hlp_ii() 。它将接受 str1,str2
- ub := str1 的大小、str2 的大小中的最小值
- cnt := 0
- 对于范围从 0 到 ub 的 i，执行
  - 如果 str1[i] 与 str2[i] 相同，则
    - cnt := cnt + 1
  - 否则，
    - 返回 cnt
  - 返回 cnt
t_dict := a new map
suff := a new list
lng := a new list
对于字符串中的每个 str，执行
- 对于范围从 0 到 str 大小的 i，执行
  - 值 := str[从索引 i 到结尾]
  - 如果值不存在于 t_dict 中，则
    - t_dict[值] := 1
    - 在 suff 末尾插入值
对列表 suff 进行排序
suff_len := size of suff
对于 i 在 0 到 suff_len 大小的范围内，执行
- 如果 i 与 0 相同，则
  - 在 lng 末尾插入 null
- 否则，
  - 在 lng 末尾插入 hlp_ii(suff[i-1], suff[i])
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]))