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

ধরুন আমাদের কাছে শুধুমাত্র ছোট হাতের অক্ষর সহ একটি স্ট্রিং s আছে, আমাদের s-এর সর্বাধিক সংখ্যক অ-খালি সাবস্ট্রিং খুঁজে বের করতে হবে যা নিম্নলিখিত নিয়মগুলি পূরণ করে

• সাবস্ট্রিংগুলি অ-ওভারল্যাপিং

• একটি সাবস্ট্রিং যা একটি নির্দিষ্ট অক্ষর ch ধারণ করে ch এর সমস্ত উপস্থিতি অবশ্যই থাকতে হবে।

আমাদের এই দুটি শর্ত পূরণ করে এমন সর্বোচ্চ সংখ্যক সাবস্ট্রিং খুঁজে বের করতে হবে। যদি একই সংখ্যক সাবস্ট্রিং সহ একাধিক সমাধান থাকে, তাহলে ন্যূনতম মোট দৈর্ঘ্য সহ সেটি ফিরিয়ে দিন।

সুতরাং, যদি ইনপুটটি s ="pqstpqqprrr" এর মত হয়, তাহলে আউটপুট হবে ["s","t","rrr"] কারণ শর্ত পূরণকারী সম্ভাব্য সমস্ত সাবস্ট্রিং হল [ "pqstpqqprrr", "pqstpqqp" , "st", "s", "t", "rrr"]

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

• ডানে :=s

  এর ডান থেকে সমস্ত পৃথক অক্ষর ch এর সূচক অবস্থানের তালিকা সাজান

• বাম :=ডানদিকের সকল i জন্য s[i] অক্ষরের সূচকের একটি তালিকা

• আছে :=একটি খালি তালিকা, gen :=একটি খালি তালিকা

• আমি 0 থেকে ডান - 1 এর সীমার মধ্যে, কর

  • gen এর শেষে s[right[i]] থেকে অক্ষরের একটি নতুন সেট সন্নিবেশ করুন

  • has

    এর শেষে s[সূচী থেকে (বাম[i] + 1 থেকে ডানে[i]-1] - gen এর শেষ আইটেম) এর সাবস্ট্রিং থেকে অক্ষরের একটি নতুন সেট সন্নিবেশ করান

  • j-এর জন্য আছে - 2 থেকে 0 এর পরিসরের আকার, 1 দ্বারা হ্রাস করুন, করুন

    • যদি (has AND gen[j] এর শেষ আইটেম) এবং (has[j] AND gen এর শেষ আইটেম) অ-শূন্য হয়, তাহলে

      • gen এর শেষ আইটেম :=gen বা gen[j]

        এর শেষ আইটেম

      • has এর শেষ আইটেম :=(has OR has[j] এর শেষ আইটেম) - gen এর শেষ আইটেম

      • রিমুভ করেছে [j], gen[j]

• res :=একটি নতুন তালিকা, p_right :=-1

• ind-এর জন্য রেঞ্জ 0 থেকে has - 1 , do

  • l :=gen[ind]

    এ s[i] উপস্থিত থাকলে বাম দিকের সকল i-এর জন্য উপাদানের তালিকার ন্যূনতম i

  • r :=gen[ind]]

    এ s[i] ডানে সব i জন্য উপাদানের তালিকার সর্বোচ্চ i

  • যদি p_right

    • res এর শেষে s[সূচী l থেকে r] এর সাবস্ট্রিং সন্নিবেশ করুন

    • p_right :=r

• রিটার্ন রিটার্ন

উদাহরণ

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

def solve(s):
   right = sorted([s.rindex(ch) for ch in set(s)])
   left = [s.index(s[i]) for i in right]
 
   has, gen = [], []
   for i in range(len(right)):
      gen.append(set(s[right[i]]))
      has.append(set(s[left[i] + 1:right[i]]) - gen[-1])

   for j in range(len(has) - 2, -1, -1):
      if (has[-1] & gen[j]) and (has[j] & gen[-1]):
         gen[-1] = gen[-1] | gen[j]
         has[-1] = (has[-1] | has[j]) - gen[-1]
         del has[j], gen[j]

   res, p_right = [], -1
   for ind in range(len(has)):
      l = min([i for i in left if s[i] in gen[ind]])
      r = max([i for i in right if s[i] in gen[ind]])
      if p_right < l:
         res.append(s[l : r + 1])
         p_right = r

   return res

s = "pqstpqqprrr"
print(solve(s))

ইনপুট

"pqstpqqprrr"

আউটপুট

['s', 't', 'rrr']