Tìm chuỗi con dài nhất là tiền tố, hậu tố và xuất hiện bên trong chuỗi trong Python

Cho chuỗi, tìm chuỗi con dài nhất vừa là tiền tố, vừa là hậu tố, vừa xuất hiện ở giữa chuỗi. Nếu không có, trả về -1.

Ví dụ: "languagepythonlanguageinterestinglanguage" → "language".

Giải thuật (KMP - LPS Array)

• Tính mảng LPS (Longest Prefix Suffix) cho chuỗi.
• LPS[n-1] là độ dài tiền tố/hậu tố dài nhất chung.
• Kiểm tra xem độ dài này có xuất hiện ở giữa chuỗi không (tìm trong LPS[0..n-2]).
• Nếu có → trả về chuỗi con độ dài đó.
• Nếu không → thử với LPS[LPS[n-1]-1] (tiền tố/hậu tố ngắn hơn).

Ví dụ

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[:lps[i]]
    if lps[lps[n - 1] - 1] == 0:
        return -1
    return string[:lps[lps[n - 1] - 1]]

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

Đầu vào

"languagepythonlanguageinterestinglanguage"

Đầu ra

language