Pythonのさまざまなクエリの文字列のさまざまなサブ文字列の数を見つけるプログラム

長さがnの文字列sがあるとします。クエリQのリストもあります。ここで、Q [i]にはペア（l、r）が含まれています。クエリごとに、lからrまでの包括的範囲内のsの異なるサブストリングの数をカウントする必要があります。

したがって、入力がs ="ppqpp" Q =[（1,1）、（1,4）、（1,1）、（0,2）]の場合、出力は[1,8、 1,5]なぜなら

• クエリ（1、1）の場合、部分文字列は「p」のみであるため、出力は1です

• クエリ（1、4）の場合、部分文字列は'p'、'q'、'pq'、'qp'、'pp'、'pqp'、'qpp'、および'pqpp'であるため、出力は8

• ここでもクエリ（1、1）の場合、部分文字列は「p」のみであるため、出力は1です

• クエリ（0、2）の場合、サブ文字列は「p」、「q」、「pp」、「pq」、「ppq」であるため、出力は8です。

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

• 関数kasai（）を定義します。これにはs、suff、nが必要です
• lcp：=サイズnの配列で、0で埋めます
• inv：=サイズnの配列で、0で埋めます
• 0からn-1の範囲のiの場合、do
  • inv [suff [i]]：=i
• k：=0
• 0からn-1の範囲のiの場合、do
  • inv [i]がn-1と同じ場合、
    • k：=0
    • 次の反復に進む
  • j：=suff [inv [i] + 1]
  • i +k
  • k：=k + 1
• lcp [inv [i]]：=k
• k> 0の場合、
  • k：=k-1

例

理解を深めるために、次の実装を見てみましょう-

def kasai (s, suff, n):
   lcp = [0] * n
   inv = [0] * n
   for i in range (n):
      inv [suff [i]] = i
   k = 0
   for i in range (n):
      if inv [i] == n-1:
         k = 0
         continue
      j = suff [inv [i] + 1]
      while i + k <n and j + k <n and s [i + k] == s [j + k]:
         k += 1
      lcp [inv [i]] = k
      if k> 0:
         k -= 1
   return lcp

def solve(s, Q):
   res = []
   for i in range (len(Q)):
      left, right = Q[i]
      sub = s [left: right + 1]
      length = right-left + 1

      suffix = [[i, sub [i:]] for i in range (length)]

      suffix.sort (key = lambda x: x [1])
      suff, suffix = [list (t) for t in zip (* suffix)]

      lcp = kasai (sub, suff, length)
      count = len (suffix [0])
      for i in range (length-1):
         count += len (suffix [i + 1]) - lcp [i]

      res.append(count)
   return res

s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q))

入力

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

出力

[1, 8, 1, 5]