পাইথনে প্রতিটি প্রশ্নের জন্য অনুরূপ সাবস্ট্রিংগুলির সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে দুটি স্ট্রিং s এবং একটি ক্যোয়ারী Q আছে। যেখানে Q[i] এ জোড়া (l, r) রয়েছে, l থেকে r পর্যন্ত s-এর প্রতিটি সাবস্ট্রিংয়ের জন্য, আমাদের x থেকে y পর্যন্ত সাবস্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে যেখানে তারা একইরকম. দুটি স্ট্রিং s এবং t একই রকম যদি তারা এই নিয়মগুলি মেনে চলে -

• তারা একই দৈর্ঘ্যের হয়

• প্রতিটি জোড়া সূচকের জন্য (i, j), যদি s[i] s[j] এর মতো হয়, তাহলে এটি অবশ্যই t[i] =t[j] পূরণ করবে, এবং একইভাবে যদি s[i] s-এর মতো না হয় [j], তারপর t[i] এবং t[j] আলাদা হতে হবে।

সুতরাং, ইনপুট যদি s ="hjhhbcbk" Q =[(1,2), (2,4)] এর মত হয়, তাহলে আউটপুট হবে [6, 1] কারণ

• প্রথম প্রশ্নের জন্য অনুরূপ সাবস্ট্রিংগুলি হল "hj", "jh", "hb", "bc", "cb" এবং "bk"।
• প্রথম প্রশ্নের জন্য অনুরূপ সাবস্ট্রিং হল "jhh"

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

• fp :=একটি নতুন তালিকা
• একটি ফাংশন সংজ্ঞায়িত করুন calc_fingerprint()। এটি s
লাগবে
• dict :=একটি নতুন অভিধান, এবং প্রাথমিকভাবে কী-মান জোড়া সন্নিবেশ করান (s[0], 0)
• fp :="0"
• j :=1
• এর জন্য 1 থেকে s - 1 এর আকারের মধ্যে, কর
  • যদি s[i] dict-এ উপস্থিত না থাকে, তাহলে
    • ডিক্ট[s[i]] :=j
    • j =j+1
  • fp :=fp + dict[s[i]] এর স্ট্রিং উপস্থাপনা
• fp-এর পূর্ণসংখ্যা ফর্ম ফেরত দিন
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• যদি s> 10 এর আকার হয়, তাহলে
  • আমি 0 থেকে s - 10 এর পরিসরের জন্য, কর
    • x :=calc_fingerprint(s[index i থেকে i+9])
    • fp-এর শেষে x ঢোকান
• ret :=একটি নতুন তালিকা
• আমি 0 থেকে Q - 1 এর আকারের জন্য,
  করুন
  • (a, b) :=Q[i]
  • s1 :=সূচী a-1 থেকে b-1 পর্যন্ত s এর সাবস্ট্রিং
  • k :=0
  • আমি 0 থেকে s - (b-a) এর পরিসরে, do
    • যদি b-a> 9 এবং fp[a-1] fp[i] এর মত না হয়, তাহলে
      • পরবর্তী পুনরাবৃত্তির জন্য যান
    • dict :=একটি নতুন খালি মানচিত্র
    • s2 :=সূচী i থেকে i+(b-a) পর্যন্ত s এর সাবস্ট্রিং
    • আমি 0 থেকে b-a রেঞ্জের জন্য, কর
      • যদি s2[i] dict-এ না থাকে, তাহলে
        • যদি s1[i] dict-এর মান থাকে, তাহলে
          • লুপ থেকে বেরিয়ে আসুন
        • ডিক্ট[s2[i]] :=s1[i]
      • যদি dict[s2[i]] s1[i] এর মত না হয়, তাহলে
        • লুপ থেকে বেরিয়ে আসুন
    • অন্যথায়,
      • k :=k + 1
  • ret এর শেষে k ঢোকান
• রিটার্ন রিটার্ন

উদাহরণ

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

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))

ইনপুট

"hjhhbcbk", [(1,2), (2,4)]

আউটপুট

[6, 1]