পাইথনে সাবস্ট্রিং সেট থেকে নির্দিষ্ট পজিশনের সাবস্ট্রিং বের করার প্রোগ্রাম

ধরুন আমাদের n সংখ্যক স্ট্রিং দেওয়া আছে: str1, str2, ..., strn। এখন substri হলো একটি সেট যাতে stri-এর সব সাবস্ট্রিং রয়েছে। সব substri-র ইউনিয়ন হলো substr_union। আমাদের q সংখ্যক কোয়েরি দেওয়া আছে, আমাদের substr_union-এর q-তম এলিমেন্ট বের করতে হবে। সেটটি লেক্সিকোগ্রাফিক্যালি সর্টেড এবং ইন্ডেক্স ১ থেকে শুরু হয়।

উদাহরণস্বরূপ, যদি স্ট্রিং লিস্ট ['pqr', 'pqt'] এবং কোয়েরি [4, 7, 9] হয়, তবে আউটপুট হবে ['pqt', 'qt', 't']।

প্রথম স্ট্রিংর সাবস্ট্রিংস: {p, pq, pqr, q, qr, r}, দ্বিতীয় স্ট্রিংর: {p, pq, pqt, q, qt, t}।

ইউনিয়ন: {p, pq, pqr, pqt, q, qr, qt, r, t}।

ইন্ডেক্স ৪, ৭, ৯-এ রয়েছে 'pqt', 'qt', 't'।

সমাধানের ধাপসমূহ

• সभी স্ট্রিংর সব সাফিক্স কले্ক্ট করুন এবং ডুপ্লিকেট সরিয়ে সর্ট করুন
• hlp_ii() ফাংশন দিয়ে দুটি স্ট্রিংর কমন প্রিফিক্স দৈর্ঘ্য বের করুন
• lng_i() ফাংশন দিয়ে সাফিক্স অ্যারে এবং LCP অ্যারে ব্যবহার করে k-তম সাবস্ট্রিং বের করুন
• প্রতিটি কোয়েরির জন্য ফলাফল রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝার জন্য:

def lng_i(suff, lng, i):
    d = zip(suff, lng)
    lo = hi = 0
    for suf, lng in d:
        if lng is None:
            lng = 0
        hi += len(suf) - lng
        if hi - 1 == i:
            return suf
        elif hi - 1 > i:
            for p, q in enumerate(list(range(lng, len(suf)))):
                if lo + p == i:
                    return suf[:q+1]
        lo = hi
    return False

def hlp_ii(str1, str2):
    ub = min(len(str1), len(str2))
    cnt = 0
    for i in range(ub):
        if str1[i] == str2[i]:
            cnt += 1
        else:
            return cnt
    return cnt

def solve(strings, q_list):
    t_dict = {}
    suff = []
    lng = []
    for str in strings:
        for i in range(len(str)):
            value = str[i:]
            if value not in t_dict:
                t_dict[value] = 1
                suff.append(value)
    suff.sort()
    suff_len = len(suff)
    for i in range(suff_len):
        if i == 0:
            lng.append(None)
        else:
            lng.append(hlp_ii(suff[i-1], suff[i]))
    res = []
    for q in q_list:
        res.append(lng_i(suff, lng, q-1))
    return res

print(solve(['pqr', 'pqt'], [4, 7, 9]))

ইনপুট

['pqr', 'pqt'], [4, 7, 9]

আউটপুট

['pqt', 'qt', 't']