在Python中查找给定位置处所有可能子字符串的给定字符串的子字符串程序

假设我们提供n个字符串; str1，str2，str3，…..，strn。现在，假设substri是包含stri的所有子字符串的集合。所有子字符串集的联合是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
- 对于i从0到ub，执行以下操作
  - 如果str1[i]与str2[i]相同，则
  - cnt：cnt + 1
  - 否则，
  - 返回cnt
  - 返回cnt
t_dict：一个新映射
suff：一个新列表
lng：一个新列表
对于字符串中的每个str，执行以下操作
- 对于i从0到str的大小，执行以下操作
  - value：str [从索引i到结束]
  - 如果value不在t_dict中，则
  - t_dict [value]：= 1
  - 在suff末尾插入value
- 对列表suff进行排序
- suff_len：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]))