ค้นหาสตริงย่อยที่ยาวที่สุดซึ่งเป็นคำนำหน้า คำต่อท้าย และยังมีอยู่ภายในสตริงใน Python

สมมติว่าเรามีสตริงที่กำหนด เราต้องหาสตริงย่อยที่ใหญ่ที่สุดซึ่งเป็นคำนำหน้า คำต่อท้าย และสตริงย่อยของสตริงที่กำหนด หากไม่มีสตริงย่อยดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือน "languagepythonlanguageinterestinglanguage" ผลลัพธ์จะเป็น "ภาษา"

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

• กำหนดฟังก์ชัน get_lps() นี่จะใช้สตริง

• n :=ขนาดของสตริง

• long_pref_suff :=อาร์เรย์ขนาด n และเติม 0

• ขนาด :=0, long_pref_suff[0] :=0, ผม :=1

• ในขณะที่ i

  • ถ้า string[i] เหมือนกับ string[size] แล้ว

    • ขนาด :=ขนาด + 1

    • long_pref_suff[i] :=ขนาด

    • ผม :=ผม + 1

  • มิฉะนั้น

    • หากขนาดไม่เท่ากับ 0 แสดงว่า

      • size :=long_pref_suff[size - 1]

    • มิฉะนั้น

      • long_pref_suff[i] :=0

      • ผม :=ผม + 1

• ส่งคืน long_pref_suff

• จากวิธีหลัก ให้ทำดังนี้ −

• long_pref_suff :=get_lps(สตริง)

• n :=ขนาดของสตริง

• ถ้า long_pref_suff[n - 1] เหมือนกับ 0 แล้ว

  • กลับ -1

• สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ

  • ถ้า long_pref_suff[i] เหมือนกับ long_pref_suff[n - 1] แล้ว

    • ส่งคืนสตริงย่อยของสตริง[จากดัชนี 0 ถึง long_pref_suff[i]]

• ถ้า long_pref_suff[long_pref_suff[n - 1] - 1] เหมือนกับ 0 แล้ว

  • กลับ -1

• มิฉะนั้น

  • ส่งคืนสตริงย่อยของสตริง[จากดัชนี 0 ถึง long_pref_suff[long_pref_suff[n - 1] - 1]]

ตัวอย่าง

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

def get_lps(string):
   n = len(string)
   long_pref_suff = [0 for i in range(n)]
   size = 0
   long_pref_suff[0] = 0
   i = 1
   while (i < n):
      if (string[i] == string[size]):
         size += 1
         long_pref_suff[i] = size
         i += 1
      else:
         if (size != 0):
            size = long_pref_suff[size - 1]
         else:
            long_pref_suff[i] = 0
            i += 1
   return long_pref_suff
def get_longest_substr(string):
   long_pref_suff = get_lps(string)
   n = len(string)
   if (long_pref_suff[n - 1] == 0):
      return -1
   for i in range(0,n - 1):
      if (long_pref_suff[i] == long_pref_suff[n - 1]):
         return string[0:long_pref_suff[i]]
      if (long_pref_suff[long_pref_suff[n - 1] - 1] == 0):
         return -1
      else:
         return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]]

string = "languagepythonlanguageinterestinglanguage"
print(get_longest_substr(string))

อินพุต

"languagepythonlanguageinterestinglanguage"

ผลลัพธ์

language