পাইথনে স্ট্রিং-র প্রিফিক্স, সাফিক্স ও ভেতরে রহা দীর্ঘতম সাবস্ট্রিং

একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-র একটি সাবস্ট্রিং খুঁজে বের করতে হবে যা একসাথে প্রিফিক্স (prefix), সাফিক্স (suffix) এবং স্ট্রিং-র ভেতরে (middle-এ) উপস্থিত থাকে। সবচেয়ে দীর্ঘ এমন সাবস্ট্রিং ফেরত দিন। না থাকলে -1।

উদাহরণ

ইনপুট: "languagepythonlanguageinterestinglanguage"

আউটপুট: "language"

সমাধানের পদ্ধতি

1. KMP অ্যালগরিদমের LPS (Longest Prefix Suffix) অ্যারে বানানো হয়।
2. LPS[n-1] দিয়ে পুরো স্ট্রিং-র দীর্ঘতম প্রিফিক্স-সাফিক্স দৈর্ঘ্য পাওয়া যায়।
3. এই দৈর্ঘ্যের সাবস্ট্রিং যদি স্ট্রিং-র মাঝপথে (০ থেকে n-2 ইনডেক্স পর্যন্ত) পাওয়া যায়, তবে সেটিই উত্তর।
4. না পেলে, LPS[LPS[n-1]-1] দিয়ে ছোটটা চেষ্টা করা হয়।

পাইথন কোড

def get_lps(string):
    n = len(string)
    long_pref_suff = [0] * 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(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