পাইথনে একটি নির্দিষ্ট স্ট্রিং ধারণকারী ক্ষুদ্রতম সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে। আমাদেরকে s-এ ক্ষুদ্রতম সাবস্ট্রিং খুঁজে বের করতে হবে, যেখানে tও সাবস্ট্রিং-এর একটি অনুবর্তী। যদি এই ধরনের সাবস্ট্রিং বিদ্যমান না থাকে, তাহলে আমরা একটি ফাঁকা স্ট্রিং ফেরত দেব, এবং যদি একাধিক ক্ষুদ্রতম সাবস্ট্রিং থাকে, তাহলে আমরা সবচেয়ে বাম স্ট্রিং নেব।

সুতরাং, যদি ইনপুটটি s ="abcbfbghfb", t ="fg" এর মত হয়, তাহলে আউটপুট হবে fbg

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

• N :=S

  এর আকার

• dp :=ইনফিনিটি দিয়ে শুরু করা N আকারের একটি নতুন তালিকা

• আমি 0 থেকে N − 1 রেঞ্জের জন্য, কর

  • যদি S[i] T[0] এর মত হয়, তাহলে

    • dp[i] :=1

• j এর জন্য রেঞ্জ 1 থেকে T − 1 এর আকার, করুন

  • শেষ :=একটি নতুন মানচিত্র

  • dp2 :=আকার N এর একটি নতুন তালিকা ইনফিনিটি দিয়ে শুরু করা হয়েছে

  • i 0 থেকে N রেঞ্জের জন্য, করুন

    • যদি S[i] T[j] এর মত হয়, তাহলে

      • prev_i :=শেষ

        থেকে T[j − 1] এর মান ফেরত দিন

      • যদি prev_i শূন্য না হয়, তাহলে

        • dp2[i] :=dp[prev_i] + (i − prev_i)

      • শেষ [S[i]] :=i

    • dp :=dp2

• m :=ন্যূনতম dp

• i :=dp এ m যুক্ত সূচী ফেরত দিন

• যদি m অসীম হয়, তাহলে

  • ফাঁকা স্ট্রিং ফেরত দিন

• S[সূচি i − dp[i] + 1 থেকে i]

  ফেরত দিন

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

উদাহরণ

class Solution:
   def solve(self, S, T):
      INF = float("inf")
      N = len(S)
      dp = [INF] * N
      for i in range(N):
         if S[i] == T[0]:
            dp[i] = 1
      for j in range(1, len(T)):
         last = {}
         dp2 = [INF] * N
         for i in range(N):
            if S[i] == T[j]:
               prev_i = last.get(T[j − 1], None)
               if prev_i is not None:
                  dp2[i] = dp[prev_i] + (i − prev_i)
            last[S[i]] = i
         dp = dp2
      m = min(dp)
      i = dp.index(m)
      if m == INF:
         return ""
      return S[i − dp[i] + 1 : i + 1]
ob = Solution()
print(ob.solve("abcbfbghfb","fg"))

ইনপুট

"abcbfbghfb","fg"

আউটপুট

fbg