Pythonで等しい部分文字列のペアの数を見つけるプログラム

両方とも小文字のアルファベットで作られた2つの文字列が与えられたとします。与えられた条件を満たす四重項（p、q、r、s）の数を見つける必要があります-

• 0 <=p <=q<=最初の文字列の長さ。

• 0 <=r <=s<=2番目の文字列の長さ。

• 最初の文字列のインデックスpで始まり、最初の文字列のインデックスqで終わる部分文字列は、2番目の文字列のインデックスqで始まり、2番目の文字列のインデックスrで終わる部分文字列と等しくなければなりません。

• q --rは、上記を満たすすべての4倍の範囲内で可能な最小値である必要があります。

そのような4倍の数を調べなければなりません。

したがって、入力がfirstString ='hgfn'、secondString ='gfrt'の場合、出力は2になります。

条件を満たし、q --rの最小値を持つ2つの4つ（1、1、0、0）と（2、2、1、1）があります。

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

• 関数ord（）を定義します。これにはch
  かかります
  • chのUnicode値を返す
• メインの方法から次のようにします-
• 左：=値の無限大を含むサイズ26の新しいリスト
• right：=値-1を含むサイズ26の新しいリスト
• res：=0
• mi：=無限大
• 各インデックスi、およびfirstStringの文字chに対して、do
  • left [ord（ch）-ord（'a'）]：=最小値（left [ord（ch）-ord（'a'）]、i）
• 各インデックスi、およびsecondStringの文字chに対して、do
  • right [ord（ch）-ord（'a'）]：=最大のright [ord（ch）-ord（'a'）]、i
• 0〜25の範囲のiの場合は、
  • left [i]が-1と同じでない場合、
    • mi：=最小値（mi、left [i] --right [i]）
• 0〜25の範囲のiの場合は、
  • left [i]が無限大と同じでなく、right [i]が-1と同じでない場合、
    • left [i] --right [i]がmiと同じ場合、
      • res：=res + 1
• return res

例

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

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

入力

'hgfn', 'gfrt'

出力

2