Chương trình đếm các chuỗi con khác nhau một ký tự trong Python

Giả sử chúng ta có hai chuỗi s và t, chúng ta phải tìm số cách chúng ta có thể chọn một chuỗi con không rỗng của s và thay thế một ký tự đơn bằng một ký tự khác sao cho chuỗi con thu được là một trong các chuỗi con của t. Chúng ta phải tìm số chuỗi con thỏa mãn điều kiện trên.

Vì vậy, nếu đầu vào giống như s ="sts" t ="tsts", thì đầu ra sẽ là 6 vì sau đây là các cặp chuỗi con từ s và t khác nhau 1 ký tự -

• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts")

Các phần ký tự in đậm là các chuỗi con được chọn từ hai chuỗi s và t.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n1:=kích thước của s
• n2:=kích thước của t
• ans:=0
• đối với mỗi chỉ mục i1 và ký tự c1 từ s, thực hiện
  • đối với mỗi chỉ mục i2 và ký tự c2 từ t, thực hiện
    • i:=i1, j:=i2
    • trong khi i
    • i:=i + 1, j:=j + 1
  • nếu i
  • :=i + 1, j:=j + 1
  • ans:=ans + 1
  • trong khi i
  • i:=i + 1, j:=j + 1
  • ans:=ans + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"sts", "tsts"

Đầu ra

6