Pythonで1文字異なる部分文字列をカウントするプログラム

2つの文字列sとtがあるとすると、空でないsの部分文字列を選択し、結果の部分文字列がtの部分文字列の1つになるように、1つの文字を別の別の文字に置き換える方法をいくつか見つける必要があります。上記の条件を満たす部分文字列の数を見つける必要があります。

したがって、入力がs ="sts" t ="tsts"の場合、出力は6になります。これは、以下が1文字だけ異なるsとtのサブストリングのペアであるためです-

• （ "sts"、 "tsts"）、
• （ "sts"、 "tsts"）、
• （ "sts"、 "tsts"）、
• （ "sts"、 "tsts"）、
• （ "sts"、 "tsts"）、
• （ "sts"、 "tsts"）

太字の部分は、2つの文字列sとtから選択された部分文字列です。

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

• n1：=sのサイズ
• n2：=tのサイズ
• ans：=0
• sの各インデックスi1と文字c1について、実行します
  • 各インデックスi2、およびtの文字c2について、実行します
    • i：=i1、j：=i2
    • i
    • i：=i + 1、j：=j + 1
  • i
  • ：=i + 1、j：=j + 1
  • ans：=ans + 1
  • i
  • i：=i + 1、j：=j + 1
  • ans：=ans + 1

例

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

def solve(s, t):
   n1 = len(s)
   n2 = len(t)
   ans = 0

   for i1, c1 in enumerate(s):
      for i2, c2 in enumerate(t):
         i = i1
         j = i2

         while i < n1 and j < n2 and s[i] == t[j]:
            i += 1
            j += 1

         if i < n1 and j < n2 and s[i] != t[j]:
            i += 1
            j += 1
            ans += 1
            while i < n1 and j < n2 and s[i] == t[j]:
               i += 1
               j += 1
               ans += 1

   return ans

s = "sts"
t = "tsts"
print(solve(s, t))

入力

"sts", "tsts"

出力

6