โปรแกรมที่จะทำการบีบอัดคำนำหน้าจากสองสตริงใน Python

สมมติว่าเรามีสองสตริง s และ t (ทั้งคู่มีตัวอักษรภาษาอังกฤษตัวพิมพ์เล็ก) เราต้องหารายชื่อคู่ขนาด 3 โดยที่แต่ละคู่อยู่ในรูปแบบนี้ (l, k) โดยที่ k คือสตริง และ l คือความยาว ในสามคู่นี้ คู่แรกมีสตริงย่อยของ s และ t ซึ่งเป็นคำนำหน้าทั่วไปที่ยาวที่สุดของ p ของสองสตริงนี้ จากนั้นส่วนที่เหลือของ s คือ s' และส่วนที่เหลือของ t คือ t' ดังนั้นรายการสุดท้ายจะเป็นเช่น [(length of p, p), (length of s', s'), (length of t', t')].

ดังนั้น หากอินพุตเป็น s ="science" t ="school" ผลลัพธ์จะเป็น [(2, 'sc'), (5, 'ience'), (4, 'hool')]

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

• lcp :=สตริงว่าง
• สำหรับ i ในช่วง 0 ถึงขนาดต่ำสุดของ s หรือขนาดของ t ให้ทำ
  • ถ้า s[i] เหมือนกับ t[i] แล้ว
    • lcp :=lcp + s[i]
• s_rem :=สตริงย่อยของ s จากดัชนี (ขนาดของ lcp) ถึงจุดสิ้นสุด
• t_rem :=สตริงย่อยของ t จากดัชนี (ขนาดของ lcp) ถึงจุดสิ้นสุด
• ส่งคืนรายการสามคู่ [(ขนาดของ lcp , lcp) ,(ขนาดของ s_rem , s_rem) ,(ขนาดของ t_rem , t_rem)]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s, t):
   lcp = ''
   for i in range(min(len(s), len(t))):
      if s[i] == t[i]:
         lcp += s[i]

   s_rem = s[len(lcp):]
   t_rem = t[len(lcp):]
   return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]

s = "science"
t = "school"
print(solve(s, t))

อินพุต

"science", "school"

ผลลัพธ์

[(2, 'sc'), (5, 'ience'), (4, 'hool')]