Pythonの各クエリの類似したサブストリングの数をカウントするプログラム

2つの文字列sとクエリQのセットがあるとします。Q[i]にペア（l、r）が含まれている場合、lからrまでのsの各部分文字列について、xからyまでの部分文字列sの数を見つける必要があります。似ています。 2つの文字列sとtは、これらのルールに従っている場合は類似しています-

• それらは同じ長さです

• インデックス（i、j）の各ペアについて、s[i]がs[j]と同じである場合、t [i] =t [j]を満たす必要があり、同様にs[i]がsと同じでない場合[j]の場合、t[i]とt[j]は異なっている必要があります。

したがって、入力がs ="hjhhbcbk" Q =[（1,2）、（2,4）]の場合、出力は[6、1]になります。

• 最初のクエリでは、同様のサブ文字列は「hj」、「jh」、「hb」、「bc」、「cb」、「bk」です。
• 最初のクエリでは、同様の部分文字列は「jhh」です

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

• fp：=新しいリスト
• 関数calc_fingerprint（）を定義します。これには時間がかかります
• dict：=新しい辞書で、最初にキーと値のペア（s [0]、0）を挿入します
• fp：="0"
• j：=1
• 範囲1からs-1のサイズのiの場合、実行
  • s [i]がdictに存在しない場合、
    • dict [s [i]]：=j
    • j =j + 1
  • fp：=fp + dict [s [i]]
  の文字列表現
• 整数形式のfpを返す
• メインの方法から、次の手順を実行します-
• サイズがs>10の場合、
  • 範囲0からs-10のサイズのiの場合、do
    • x：=calc_fingerprint（s[インデックスiからi+ 9]）
    • fpの最後にxを挿入
• ret：=新しいリスト
• 範囲0からQ-1のサイズのiの場合、実行
  • （a、b）：=Q [i]
  • s1：=インデックスa-1からb-1までのsの部分文字列
  • k：=0
  • 0からsのサイズまでの範囲のiの場合-（b-a）、do
    • b-a>9でfp[a-1]がfp[i]と同じでない場合、
      • 次の反復に進む
    • dict：=新しい空のマップ
    • s2：=インデックスiからi +（b-a）までのsの部分文字列
    • 0からb-aの範囲のiについては、
      • s2 [i]がdictにない場合、
        • s1 [i]がdictの値の場合、
          • ループから抜け出す
        • dict [s2 [i]]：=s1 [i]
      • dict [s2[i]]がs1[i]と同じでない場合、
        • ループから抜け出す
    • それ以外の場合、
      • k：=k + 1
  • retの最後にkを挿入
• return ret

例

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

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

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

入力

"hjhhbcbk", [(1,2), (2,4)]

出力

[6, 1]