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

สมมติว่าเรามีสตริง ต้องการหาสตริงย่อยที่ยาวที่สุดซึ่งเป็นพร้อมกัน: คำนำหน้า (prefix), คำต่อท้าย (suffix), และปรากฏเป็นสตริงย่อยภายใน (ไม่ใช่แค่ปลาย) หากไม่มี คืนค่า -1

เช่น "languagepythonlanguageinterestinglanguage" ผลลัพธ์คือ "language"

ขั้นตอนการแก้ปัญหา (KMP LPS Array)

1. สร้างอาร์เรย์ LPS (Longest Prefix Suffix) ด้วยอัลกอริทึม KMP
2. ค่า lps[n-1] คือความยาวของคำนำหน้า/คำต่อท้ายที่ยาวที่สุด
3. ตรวจสอบว่าความยาวนี้ปรากฏในตำแหน่งกลางของอาร์เรย์ LPS หรือไม่
4. ถ้ามี คืนค่าสตริงย่อยความยาวนั้น ถ้าไม่มี ลองตรวจสอบความยาวสั้นกว่า (lps[lps[n-1]-1])

ตัวอย่างโค้ด Python

def get_lps(string):
    n = len(string)
    lps = [0] * n
    length = 0
    i = 1
    while i < n:
        if string[i] == string[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def get_longest_substr(string):
    lps = get_lps(string)
    n = len(string)
    if lps[n - 1] == 0:
        return -1
    for i in range(n - 1):
        if lps[i] == lps[n - 1]:
            return string[0:lps[i]]
    if lps[lps[n - 1] - 1] == 0:
        return -1
    else:
        return string[0:lps[lps[n - 1] - 1]]

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

อินพุต

"languagepythonlanguageinterestinglanguage"

เอาต์พุต

language