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 := 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 := 一個新的對映。
  • 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])
  • 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 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告