পাইথনে একটি স্ট্রিং এবং এর প্রত্যয়গুলির মধ্যে মিল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন, আমাদের একটি স্ট্রিং 'input_str' দেওয়া হয়েছে। যদি আমরা input_str থেকে সমস্ত প্রত্যয় নির্ধারণ করি; উদাহরণস্বরূপ, যদি স্ট্রিংটি 'abcd' হয়, প্রত্যয়গুলি 'abc', 'bcd', 'cd', 'd'। এখন, আমরা input_str এবং একটি প্রত্যয়ের দীর্ঘতম সাধারণ উপসর্গের দৈর্ঘ্য দ্বারা input_str এবং সমস্ত প্রত্যয়ের মধ্যে মিল পরীক্ষা করি। input_str এবং সমস্ত প্রত্যয়ের মধ্যে মিলের যোগফল ফেরত দিতে হবে।

সুতরাং, যদি ইনপুটটি input_str ='tpotp' এর মত হয়, তাহলে আউটপুট হবে 7

'tpotp' স্ট্রিং থেকে সমস্ত প্রত্যয় হল 'tpotp', 'potp', 'otp', 'tp', এবং 'p'।

যদি আমরা input_str এর সাথে সমস্ত প্রত্যয়ের মিল পরীক্ষা করি, তাহলে আমরা −

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0

Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• রিটার্ন_লিস্ট :=ইনপুট_স্ট্রের আকার ধারণকারী একটি নতুন তালিকা
• i :=1
• p :=0
• q :=0
• r :=0
• যখন আমি
• যদি q
• যদি return_list[i-q]>=q+p-i, তারপর
  • r :=q + p - i
  • p :=0
  • q :=0
• অন্যথায়,
  • রিটার্ন_লিস্টের শেষে [i-q] যোগ করুন
  • i :=i + 1
  • r :=0

def solve(input_str):
   return_list = [len(input_str)]
   i = 1
   p, q = 0,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'))

'tpotp'

5