C++ में सभी अच्छे स्ट्रिंग्स खोजें

मान लीजिए कि हमारे पास दो तार s1 और s2 हैं। इन तारों का आकार n है, और हमारे पास एक और तार भी है जिसे बुराई कहा जाता है। हमें अच्छे स्ट्रिंग्स की संख्या ज्ञात करनी है।

एक स्ट्रिंग को अच्छा कहा जाता है जब इसका आकार n होता है, यह वर्णानुक्रम में s1 से बड़ा या बराबर होता है, यह वर्णानुक्रम में s2 से छोटा या उसके बराबर होता है, और इसमें सबस्ट्रिंग के रूप में कोई बुराई नहीं होती है। उत्तर बहुत बड़ा हो सकता है, इसलिए उत्तर मॉड्यूल 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट n =2, s1 ="bb", s2 ="db", बुरा ="a" जैसा है, तो आउटपुट 51 होगा, क्योंकि 25 अच्छे तार हैं जो b से शुरू हो रहे हैं। "बीबी", "बीसी", "बीडी", ... "बीजेड", फिर "सीबी", "सीसी", "सीडी", ..., "सीजे", और एक और अच्छा से शुरू होने वाले 25 अच्छे तार हैं d के साथ स्ट्रिंग "db" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एन:=500, एम:=50
आकार की एक सरणी dp परिभाषित करें:(N+1) x (M+1) x 2.
आकार की एक सरणी tr परिभाषित करें:(M+1) x 26.
मी :=1^9 + 7
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा
वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें n, s, e,
. लगेगा
सरणी को उल्टा करें e
tr और dp को 0 से भरें
इनिशियलाइज़ i :=0 के लिए, जब i
- f :=इंडेक्स 0 से i - 1 में e का सबस्ट्रिंग
- इनिशियलाइज़ j :=0 के लिए, जब j <26, अपडेट करें (j को 1 से बढ़ाएँ), करें -
  - ns :=f + (j + 'a' का ASCII)
  - प्रारंभ करने के लिए k :=i + 1, (k को 1 से घटाएं), −
    . करें
    - यदि इंडेक्स (i + 1 - k) से अंत तक ns का सबस्ट्रिंग e से e के इंडेक्स 0 से k-1 के सबस्ट्रिंग के समान है, तो -
      - tr[i, j] :=k
      - लूप से बाहर आएं
मी :=ई का आकार
इनिशियलाइज़ i :=0 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
- इनिशियलाइज़ j :=0 के लिए, जब j
  - डीपी [i, जे, 0]:=0
  - डीपी [आई, जे, 1]:=0
डीपी [एन, 0, 1]:=1
इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें
- इनिशियलाइज़ j :=0 के लिए, जब j
  - इनिशियलाइज़ k :=0 के लिए, जब k <26, अपडेट करें (1 से k बढ़ाएँ), करें -
    - l के लिए रेंज में (0, 1)
      - अगर k> s[i] - 'a' का ASCII, तो -
        
        nl:=0
      - अन्यथा जब k
        
        nl:=1
      - अन्यथा
        
        nl:=एल
      - dp[i, tr[j, k], nl] :=add(dp[i, tr[j, k], nl], dp[i + 1, j, l])
रिट:=0
इनिशियलाइज़ i :=0 के लिए, जब i
- रिट:=जोड़ें (रिट, डीपी [0, आई, 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, अन्यथा हल करें (एन, एस 1, बुराई))
दाएं:=हल करें (एन, एस 2, बुराई)
वापसी (दाएं - बाएं + एम) मॉड एम

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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"