পাইথনে একটি স্ট্রিং এবং তার সাফিক্সগুলির মধ্যে সাদৃশ্যের যোগফল বের করার প্রোগ্রাম

একটি স্ট্রিং input_str দেওয়া আছে। এর সব সাফিক্স বের করে প্রতিটি সাফিক্সের সাথে মূল স্ট্রিং-এর লংগেস্ট কমন প্রিফিক্সের দৈর্ঘ্য (সাদৃশ্য) বের করতে হবে। সব সাদৃশ্যের যোগফল রিটার্ন করুন।

উদাহরণ

input_str = 'tpotp' → আউটপুট: 7

সাফিক্সগুলো: 'tpotp', 'potp', 'otp', 'tp', 'p'

সাদৃশ্য: ৫, ০, ০, ২, ০ → যোগফল = ৭

এলগরিদম (Z-অ্যালগরিদম ভিত্তিক)

1. return_list := [len(input_str)]
2. i := 1, p := 0, q := 0, r := 0
3. while i < len(input_str):
   • যদি q < i < q+p:
     • যদি return_list[i-q] >= q+p-i: r := q+p-i, p:=0, q:=0
     • অন্যথায়: return_list.append(return_list[i-q]), i++, r:=0
   • অন্যথায়:
     • while i+r < len(input_str) and input_str[r] == input_str[i+r]: r++
     • return_list.append(r), p:=r, q:=i, i++, r:=0
4. sum(return_list) রিটার্ন করুন।

পাইথন কোড

def solve(input_str):
    return_list = [len(input_str)]
    i = 1
    p = q = 0
    r = 0
    while i < len(input_str):
        if q < i < (q + p):
            if return_list[i - q] >= q + p - i:
                r = q + p - i
                p, q = 0, 0
            else:
                return_list.append(return_list[i - q])
                i += 1
                r = 0
        else:
            while i + r < len(input_str) and input_str[r] == input_str[i + r]:
                r += 1
            return_list.append(r)
            p, q = r, i
            i += 1
            r = 0
    return sum(return_list)

print(solve('tpotp'))  # আউটপুট: 7

ইনপুট / আউটপুট

'tpotp'
7