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}です。

これら2つのセットの和集合、つまりsubstr_unionは{p、pq、pqr、pqt、q、qr、qt、r、t}です。

したがって、インデックス4、7、および9の項目は、それぞれ「pqt」、「qt」、および「t」です。

これを解決するには、次の手順に従います-

• 関数lng_i（）を定義します。これには十分な時間がかかります、lng、i
  • d：=（suff、lng）を含む新しいタプル
  • lo：=0
  • こんにちは：=0
  • dのタプル（suf、lng）ごとに、
    を実行します。
    • lngがnullに類似している場合、
      • lng：=0
    • hi：=hi+sufのサイズ-lng
    • hi-1がiと同じ場合、
      • return suf
    • それ以外の場合、hi-1> iの場合、
      • lngからsufのサイズまでの値のリストのインデックスpとアイテムqについては、
        • lo + pがiと同じ場合、
          • return suf [from index 0 to j + 1]
    • lo：=hi
  • Falseを返す
• 関数hlp_ii（）を定義します。これにはstr1、str2
  がかかります
  • ub：=str1の最小サイズ、str2のサイズ
  • cnt：=0
  • 0からubの範囲のiについては、
    • str1[i]がstr2[i]と同じ場合、
      • cnt：=cnt + 1
    • それ以外の場合、
      • return cnt
    • return cnt
• t_dict：=新しい地図
• suff：=新しいリスト
• lng：=新しいリスト
• 文字列の各strについて、

  • 0からstrのサイズの範囲のiの場合、実行します

    • value：=str[インデックスiから終了まで]
    • 値がt_dictに存在しない場合、
      • t_dict [value]：=1
      • サフの最後に値を挿入
• リストを並べ替える
• 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））を挿入します
• return 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']