โปรแกรมนับสตริงย่อยที่ต่างกันหนึ่งอักขระใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องหาจำนวนวิธีที่เราสามารถเลือกสตริงย่อยที่ไม่ว่างของ s และแทนที่อักขระตัวเดียวด้วยอักขระอื่นเพื่อให้สตริงย่อยที่เป็นผลลัพธ์เป็นหนึ่งในสตริงย่อยของ t เราต้องหาจำนวนสตริงย่อยที่ตรงตามเงื่อนไขข้างต้น

ดังนั้น หากอินพุตเป็นเหมือน s ="sts" t ="tsts" ผลลัพธ์จะเป็น 6 เพราะต่อไปนี้คือคู่ของสตริงย่อยจาก s และ t ที่ต่างกัน 1 ตัวอักษร −

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

ส่วนอักขระตัวหนาคือสตริงย่อยที่เลือกจากสองสตริง s และ t

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n1 :=ขนาดของ s
• n2 :=ขนาดของเสื้อ
• ตอบ :=0
• สำหรับแต่ละดัชนี i1 และอักขระ c1 จาก s ทำ
  • สำหรับแต่ละดัชนี i2 และอักขระ c2 จาก t ทำ
    • i :=i1, j :=i2
    • ในขณะที่ i
    • i :=i + 1, j :=j + 1
  • ถ้าฉัน
  • :=i + 1, j :=j + 1
  • อัน :=ans + 1
  • ในขณะที่ i
  • i :=i + 1, j :=j + 1
  • อัน :=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