C++ এ সব ভালো স্ট্রিং খুঁজুন

ধরুন আমাদের দুটি স্ট্রিং s1 এবং s2 আছে। এই স্ট্রিংগুলির আকার হল n, এবং আমাদের আরও একটি স্ট্রিং আছে যাকে মন্দ বলা হয়। আমাদের ভালো স্ট্রিংয়ের সংখ্যা খুঁজে বের করতে হবে।

একটি স্ট্রিংকে ভাল বলা হয় যখন এর আকার n হয়, এটি বর্ণানুক্রমিকভাবে s1 এর চেয়ে বড় বা সমান হয়, এটি বর্ণানুক্রমিকভাবে s2 এর থেকে ছোট বা সমান হয় এবং সাবস্ট্রিং হিসাবে এটির কোন মন্দ নেই। উত্তরটি অনেক বড় হতে পারে, তাই উত্তর মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি n =2, s1 ="bb", s2 ="db", evil ="a" এর মত হয়, তাহলে আউটপুট হবে 51, কারণ এখানে 25টি ভাল স্ট্রিং আছে যা b দিয়ে শুরু হচ্ছে। "bb", "bc", "bd", ... "bz", তারপর "cb", "cc", "cd",...,"cz" দিয়ে শুরু করে 25টি ভালো স্ট্রিং আছে এবং আরেকটি ভালো d এর সাথে স্ট্রিং হল "db"।

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

• N :=500, M :=50

• আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:(N+1) x (M+1) x 2।

• আকারের একটি অ্যারে tr সংজ্ঞায়িত করুন:(M+1) x 26।

• মি :=1^9 + 7

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন solve() সংজ্ঞায়িত করুন, এটি n, s, e,

  লাগবে

• অ্যারে ই

  বিপরীত করুন

• 0

  দিয়ে tr এবং dp পূরণ করুন

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

  • f :=সূচক 0 থেকে i - 1

    পর্যন্ত e এর সাবস্ট্রিং

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

    • ns :=f + ('a'-এর j + ASCII)

    • আরম্ভ করার জন্য k :=i + 1, (k 1 দ্বারা কম করুন), −

      করুন

      • যদি সূচক (i + 1 - k) থেকে শেষ পর্যন্ত ns-এর সাবস্ট্রিং e-এর সূচক 0 থেকে k-1-এর সাবস্ট্রিং-এর মতো হয়, তাহলে −

        • tr[i, j] :=k

        • লুপ থেকে বেরিয়ে আসুন

• m :=e

  এর আকার

• আরম্ভ করার জন্য i :=0, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • j শুরু করার জন্য :=0, যখন j করুন

    • dp[i, j, 0] :=0

    • dp[i, j, 1] :=0

• dp[n, 0, 1] :=1

• আরম্ভ করার জন্য i :=n - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), করুন −

  • j শুরু করার জন্য :=0, যখন j করুন

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

      • l পরিসরের জন্য (0, 1)

        • যদি k> s[i] - 'a'-এর ASCII হয়, তাহলে −

          • nl :=0

        • অন্যথায় যখন k

          • nl :=1

        • অন্যথায়

          • nl :=l

        • dp[i, tr[j, k], nl] :=add(dp[i, tr[j, k], nl], dp[i + 1, j, l])

• ret :=0

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

  • ret :=add(ret, dp[0, i, 1])

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ঠিক আছে :=1

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

  • ঠিক আছে :=1 যখন s1[i] 'a'

    এর ASCII এর মত হয়

• যদি ঠিক না হয় অ-শূন্য হয়, তাহলে −

  • আরম্ভ করার জন্য i :=s1 এর আকার, যখন i>=0, আপডেট (i 1 দ্বারা হ্রাস), do−

    • যদি s1[i] 'a' এর সমান না হয়, তাহলে −

      • (s1[i] 1 দ্বারা কমিয়ে দিন)

      • লুপ থেকে বেরিয়ে আসুন

    • s1[i] :='z'

      এর ASCII

• বাম :=(যদি ঠিক থাকে অ-শূন্য, তাহলে 0, অন্যথায় সমাধান করুন(n, s1, খারাপ))

• right :=solve(n, s2, evil)

• ফিরুন (ডান - বাম + মি) মোড m

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int N = 500;
const int M = 50;
int dp[N + 1][M + 1][2];
int tr[M + 1][26];
const lli m = 1e9 + 7;
class Solution {
   public:
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   lli solve(int n, string s, string e){
      reverse(e.begin(), e.end());
      memset(tr, 0, sizeof(tr));
      memset(dp, 0, sizeof(dp));
      for (int i = 0; i < e.size(); i++) {
         string f = e.substr(0, i);
         for (int j = 0; j < 26; j++) {
            string ns = f + (char)(j + 'a');
            for (int k = i + 1;; k--) {
               if (ns.substr(i + 1 - k) == e.substr(0, k)) {
                  tr[i][j] = k;
                  break;
               }
            }
         }
      }
      int m = e.size();
      for (int i = 0; i <= n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = dp[i][j][1] = 0;
         }
      }
      dp[n][0][1] = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = 0; j < e.size(); j++) {
            for (int k = 0; k < 26; k++) {
               for (int l : { 0, 1 }) {
                  int nl;
                  if (k > s[i] - 'a') {
                     nl = 0;
                  }
                  else if (k < s[i] - 'a') {
                     nl = 1;
                  }
                  else
                  nl = l;
                  dp[i][tr[j][k]][nl] = add(dp[i][tr[j][k]]
                  [nl], dp[i + 1][j][l]);
               }
            }
         }
      }
      lli ret = 0;
      for (int i = 0; i < e.size(); i++) {
         ret = add(ret, dp[0][i][1]);
      }
      return ret;
   }
   int findGoodStrings(int n, string s1, string s2, string evil) {
      bool ok = 1;
      for (int i = 0; i < s1.size() && ok; i++) {
         ok = s1[i] == 'a';
      }
      if (!ok) {
         for (int i = s1.size() - 1; i >= 0; i--) {
            if (s1[i] != 'a') {
               s1[i]--;
               break;
            }
            s1[i] = 'z';
         }
      }
      int left = ok ? 0 : solve(n, s1, evil);
      int right = solve(n, s2, evil);
      return (right - left + m) % m;
   }
};
main(){
   Solution ob;
   cout << (ob.findGoodStrings(2, "bb", "db", "a"));
}

ইনপুট

2, "bb", "db", "a"

আউটপুট

51