পাইথনে সমান সাবস্ট্রিং জোড়ার সংখ্যা বের করার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং দেওয়া হয়েছে, উভয়ই ছোট হাতের বর্ণমালা দিয়ে তৈরি। প্রদত্ত শর্তগুলিকে সন্তুষ্ট করে আমাদের চতুর্গুণের সংখ্যা (p, q, r, s) খুঁজে বের করতে হবে −

0 <=p <=q <=প্রথম স্ট্রিংয়ের দৈর্ঘ্য।
0 <=r <=s <=দ্বিতীয় স্ট্রিংয়ের দৈর্ঘ্য।
প্রথম স্ট্রিং এর সূচী p থেকে শুরু হওয়া এবং প্রথম স্ট্রিং এর সূচী q এ শেষ হওয়া সাবস্ট্রিংটি দ্বিতীয় স্ট্রিং এর সূচী q থেকে শুরু হওয়া এবং দ্বিতীয় স্ট্রিং এর সূচী r এ শেষ হওয়া সাবস্ট্রিং এর সমান হতে হবে৷
q - r হতে হবে ন্যূনতম সম্ভাব্য মান হতে হবে উপরের সমস্ত চতুর্গুণের মধ্যে।

আমাদের এই ধরনের চারগুণ সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় firstString ='hgfn', secondString ='gfrt', তাহলে আউটপুট হবে 2।

দুটি চতুর্গুণ (1, 1, 0, 0) এবং (2, 2, 1, 1) শর্ত পূরণ করে এবং q - r-এর জন্য সর্বনিম্ন মান রয়েছে৷

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

একটি ফাংশন ক্রম() সংজ্ঞায়িত করুন। এটি ch
- ch এর ইউনিকোড মান ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
বাম :=26 আকারের একটি নতুন তালিকা যেখানে মান অসীম রয়েছে
ডান:=26 আকারের একটি নতুন তালিকা যার মান -1 রয়েছে
res :=0
mi :=অসীম

left[ord(ch) - ord('a') ] :=সর্বনিম্ন (left[ord(ch) - ord('a') ], i)

সেকেন্ডস্ট্রিং-এ প্রতিটি সূচক i, এবং অক্ষর ch-এর জন্য, করুন
- right[ord(ch) - ord('a') ] :=ডানের সর্বোচ্চ[ord(ch) - ord('a') ], i
আমি 0 থেকে 25 রেঞ্জের জন্য, কর
- যদি বাকি থাকে[i] -1 এর মত না হয়, তাহলে
  - mi :=সর্বনিম্ন (mi, left[i] - right[i])
আমি 0 থেকে 25 রেঞ্জের জন্য, কর
- যদি বাম[i] অসীমের সমান না হয় এবং ডান [i] -1 এর মতো না হয়, তাহলে
  - যদি left[i] - right[i] হয় mi এর মতো, তাহলে
    - res :=res + 1
রিটার্ন রিটার্ন

উদাহরণ

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

def solve(firstString, secondString):
   left = [float('inf')] * 26
   right = [-1] * 26
   res = 0
   mi = float('inf')
   for i, ch in enumerate(firstString):
      left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
   for i, ch in enumerate(secondString):
      right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
   for i in range(26):
      if left[i] != -1:
         mi = min(mi, left[i] - right[i])
   for i in range(26):
      if left[i] != float('inf') and right[i] != -1:
         if left[i] - right[i] == mi:
            res += 1
   return res

print(solve('hgfn', 'gfrt'))

ইনপুট

'hgfn', 'gfrt'