C++-এ লক্ষ্যের মতোই অনন্য অনুসারীর সংখ্যা খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি s ="abbd" t ="bd" এর মত হয়, তাহলে আউটপুট হবে 2, কারণ দুটি সম্ভাব্য পরবর্তী "bd"।

• s[1] concatenate s[3]

• s[2] concatenate s[3].

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

• m :=10^9 + 7

• যদি t এর আকার 0 এর সমান হয়, তাহলে −

  • রিটার্ন 0

• t যদি s এর মত হয়, তাহলে −

  • রিটার্ন 1

• যদি t এর সাইজ> s এর সাইজ হয়, তাহলে −

  • রিটার্ন 0

• t + 1 এর আকারের সমান আকারের একটি অ্যারে টেবিল সংজ্ঞায়িত করুন এবং 0

  দিয়ে পূরণ করুন

• টেবিল[0] :=1

• আরম্ভ করার জন্য i :=0, যখন i

  • একটি অ্যারে সংজ্ঞায়িত করুন onsave :=টেবিল

  • j শুরু করার জন্য :=0, যখন j <টেবিলের আকার, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −

    • যদি s[i] t[j] এর মত হয়, তাহলে −

      • টেবিল[j + 1] =(টেবিল[j + 1] mod m + অনসেভ[j] mod m)

• টেবিল[j + 1] =(টেবিল[j + 1] mod m + অনসেভ[j] mod m)

#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
   int m = 1000000007;
   if (t.size() == 0)
      return 0;
   if (t == s)
      return 1;
   if (t.size() > s.size())
      return 0;
   vector<int> table(t.size() + 1, 0);
   table[0] = 1;
   for (int i = 0; i < s.size(); i++) {
      vector<int> onsave = table;
      for (int j = 0; j < table.size(); j++) {
         if (s[i] == t[j]) {
            table[j + 1] = (table[j + 1] % m + onsave[j] % m) %m;
         }
      }
   }
   return table[t.size()] % m;
}
main(){
   string s = "abbd", t = "bd";
   cout << (solve(s, t));
}

"abbd", "bd"

2