পাইথনে স্বতন্ত্র অনুসৃতির সংখ্যা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের স্ট্রিং s-এর স্বতন্ত্র অনুগামী সংখ্যা গণনা করতে হবে। যদি উত্তরটি খুব বড় হয় তাহলে ফলাফল মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি s ="bab" এর মত হয়, তাহলে আউটপুট হবে 6 কারণ এখানে 6টি ভিন্ন ক্রম আছে, এগুলো হল "a", "b, "ba", "ab", "bb", "abb" .

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

dp :=একটি অ্যারে যার আকার s এর সমান এবং 0
দিয়ে পূর্ণ
m :=10^9 + 7
প্রতিটি সূচী i এবং আইটেম চারের জন্য s, করুন
- ind :=ডান থেকে s-এ i-ম চর-এর সূচী
- dp[i] :=1 + (dp [index 0 থেকে i-1]-এর সমস্ত উপাদানের যোগফল ]) mod m
dp mod m
-এ সমস্ত উপাদানের যোগফল ফেরত দিন

উদাহরণ

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

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))

ইনপুট

"abcd", "abcdbcd"