โปรแกรมค้นหาความยาวของสตริงย่อยที่ยาวที่สุดในสตริงใน Python

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดที่เกิดขึ้นอย่างน้อยสองครั้งใน s หากไม่พบสตริงดังกล่าว ให้คืนค่า 0

ดังนั้น หากอินพุตเป็น s ="abdgoalputabdtypeabd" ผลลัพธ์จะเป็น 3 เนื่องจากสตริงย่อยที่ยาวที่สุดที่เกิดขึ้นมากกว่าหนึ่งครั้งคือ "abd"

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

• กำหนดฟังก์ชัน lcs() นี่จะใช้เวลา s1, s2
• n :=ขนาดต่ำสุดของ s1 และขนาดของ s2
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ถ้า s1[i] ไม่เหมือนกับ s2[i] แล้ว
    • ส่งคืนสตริงย่อยของ s1[จากดัชนี 0 ถึง i-1]
• ส่งคืนสตริงย่อยของ s1[จากดัชนี 0 ถึง n - 1]
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• คำต่อท้าย :=รายการใหม่
• n :=ขนาดของ s
• max_len :=0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • แทรก (สตริงย่อยของ s[จากดัชนี i ถึง n - 1]) ที่ส่วนท้ายของส่วนต่อท้าย
• จัดเรียงคำต่อท้ายรายการ
• สำหรับแต่ละรายการ a จากส่วนต่อท้ายและ b จากสตริงย่อยของส่วนต่อท้าย[จากดัชนี 1 ถึงส่วนท้าย] ทำ
  • rtr :=lcs(a, b)
  • ถ้าขนาดของ rtr> max_len แล้ว
    • max_len :=ขนาดของ rtr
• คืน max_len

ตัวอย่าง

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

def lcs(s1, s2):
   n = min(len(s1), len(s2))

   for i in range(n):
      if s1[i] != s2[i]:
         return s1[:i]
   return s1[:n]

def solve(s):
   suffixes = []
   n = len(s)
   max_len = 0

   for i in range(n):
      suffixes.append(s[i:n])

   suffixes.sort()

   for a, b in zip(suffixes, suffixes[1:]):
      rtr = lcs(a, b)

      if len(rtr) > max_len:
         max_len = len(rtr)

   return max_len

s = "abdgoalputabdtypeabd"
print(solve(s))

อินพุต

"abdgoalputabdtypeabd"

ผลลัพธ์

3