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

ধরুন আমরা একটি স্ট্রিং s আছে. আমাদের প্রতিটি প্রত্যয় এর সাথে স্ট্রিং s এর মিলের যোগফল খুঁজে বের করতে হবে। এখানে দুটি স্ট্রিং-এর মধ্যে সাদৃশ্য হল দীর্ঘতম উপসর্গের দৈর্ঘ্য, যা উভয় স্ট্রিং-এর জন্য সাধারণ।

সুতরাং, যদি ইনপুটটি s ="pqpqpp" এর মত হয়, তাহলে আউটপুট হবে 11 কারণ স্ট্রিংয়ারের প্রত্যয় "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" এবং "p"। "pqpqpp" স্ট্রিং এর সাথে এই সাবস্ট্রিংগুলির মিল হল 6,0,3,0,1, এবং 1৷ তাই যোগফল হল 6 + 0 + 3 + 0 + 1 + 1 =11৷

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

দৈর্ঘ্য :=s এর আকার
মোট :=দৈর্ঘ্য
z :=প্রাথমিকভাবে 0 আছে এমন একটি তালিকা
l :=0, r :=0
করুন
- যদি k> r, তারপর
  - ম্যাচ:=0
  - সূচক :=k
- যখন ইনডেক্স <দৈর্ঘ্য, do
  - যদি s[index] s[match] এর মত হয়, তাহলে
    - ম্যাচ :=ম্যাচ + 1
    - সূচী :=সূচক + 1
  - অন্যথায়,
    - লুপ থেকে বেরিয়ে আসুন
- z-এর শেষে মিল ঢোকান
- যদি মেলে> 0, তারপর
  - মোট :=মোট + মিল
  - l :=k
  - r :=index-1
- অন্যথায়,
  - যদি z[k-l] <(r-k)+1 হয়, তাহলে
    - z-এর শেষে z[k-l] ঢোকান
    - মোট :=মোট + z[k-l]
  - অন্যথায়,
    - ম্যাচ :=r-k
    - সূচক :=r
    - যখন ইনডেক্স <দৈর্ঘ্য, do
      - যদি s[index] s[match] এর মত হয়, তাহলে
        
        ম্যাচ :=ম্যাচ + 1
        
        সূচী :=সূচক + 1
      - অন্যথায়,
        
        লুপ থেকে বেরিয়ে আসুন
    - z-এর শেষে মিল ঢোকান
    - মোট :=মোট + মিল
    - l :=k
    - r :=index-1
মোট রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

ইনপুট

"pqpqpp"