Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


समस्या विवरण

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

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

उदाहरण

यदि इनपुट है: n = 2, s1 = "bb", s2 = "db", evil = "a", तो आउटपुट होगा 51, क्योंकि 25 अच्छे स्ट्रिंग्स हैं जो b से शुरू होते हैं: "bb", "bc", "bd", ... "bz", फिर 25 अच्छे स्ट्रिंग्स हैं जो "cb", "cc", "cd", ..., "cz" से शुरू होते हैं, और d के साथ एक और अच्छा स्ट्रिंग है "db"।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (KMP ऑटोमेटन + DP):

  • N := 500, M := 50
  • आकार (N+1) x (M+1) x 2 का एक सरणी dp परिभाषित करें
  • आकार (M+1) x 26 का एक सरणी tr परिभाषित करें
  • m := 10^9 + 7
  • add() नामक एक फ़ंक्शन परिभाषित करें, जो a, b लेता है:
    • ((a % m) + (b % m)) % m लौटाएं
  • solve() नामक एक फ़ंक्शन परिभाषित करें, जो n, s, e लेता है:
    • सरणी e को रिवर्स करें
    • tr और dp को 0 से भरें
    • i := 0 से आरंभ करें, जब i < e का आकार, i को 1 से बढ़ाते हुए:
      • f := e का सबस्ट्रिंग इंडेक्स 0 से i-1 तक
      • j := 0 से आरंभ करें, जब j < 26, j को 1 से बढ़ाते हुए:
        • ns := f + (j + 'a' का ASCII)
        • k := i + 1 से आरंभ करें, (k को 1 से घटाते हुए):
          • यदि ns का सबस्ट्रिंग इंडेक्स (i + 1 - k) से अंत तक, e के सबस्ट्रिंग इंडेक्स 0 से k-1 के समान है:
            • tr[i][j] := k
            • लूप से बाहर निकलें
    • m := e का आकार
    • i := 0 से आरंभ करें, जब i <= n, i को 1 से बढ़ाते हुए:
      • j := 0 से आरंभ करें, जब j < m, j को 1 से बढ़ाते हुए:
        • 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 < e का आकार, j को 1 से बढ़ाते हुए:
        • k := 0 से आरंभ करें, जब k < 26, k को 1 से बढ़ाते हुए:
          • l के लिए रेंज (0, 1) में:
            • यदि k > s[i] - 'a' का ASCII:
              • nl := 0
            • अन्यथा यदि k < s[i] - 'a' का ASCII:
              • 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 < e का आकार, i को 1 से बढ़ाते हुए:
      • ret := add(ret, dp[0][i][1])
    • ret लौटाएं
  • मुख्य विधि से:
    • ok := 1
    • i := 0 से आरंभ करें, जब i < s1 का आकार और ok शून्येतर है, i को 1 से बढ़ाते हुए:
      • ok := 1 जब s1[i] 'a' के ASCII के समान है
    • यदि ok शून्येतर नहीं है:
      • i := s1 के आकार से आरंभ करें, जब i >= 0, i को 1 से घटाते हुए:
        • यदि s1[i] 'a' के समान नहीं है:
          • s1[i] को 1 से घटाएं
          • लूप से बाहर निकलें
        • s1[i] := 'z' का ASCII
    • left := (यदि ok शून्येतर है तो 0, अन्यथा solve(n, s1, evil))
    • right := solve(n, s2, evil)
    • (right - left + m) % m लौटाएं

C++ कार्यान्वयन

#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;
    }
};

int main() {
    Solution ob;
    cout << (ob.findGoodStrings(2, "bb", "db", "a"));
    return 0;
}

इनपुट

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

आउटपुट

51
  1. C++ में सभी डुप्लिकेट सबट्री खोजें C++ में सभी डुप्लिकेट सबट्री खोजें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह पता लगाना है कि ट्री में कुछ डुप्लिकेट सबट्री हैं या नहीं। मान लीजिए हमारे पास नीचे जैसा बाइनरी ट्री है: आकार 2 के दो समान सबट्री हैं। प्रत्येक सबट्री में D, BD और BE भी डुप्लिकेट सबट्री हैं। हम इस समस्या को ट्री सीरियलाइज़ेशन और हैशिंग प्रक्रिया का उ

  1. - C++ में स्ट्रिंग्स की सरणी

    इस खंड में हम देखेंगे कि C++ में स्ट्रिंग्स की सरणी को कैसे परिभाषित किया जाए। जैसा कि हम जानते हैं कि C में कोई स्ट्रिंग्स नहीं थीं। हमें कैरेक्टर सरणी का उपयोग करके स्ट्रिंग्स बनानी पड़ती थीं। इसलिए कुछ स्ट्रिंग्स की सरणी बनाने के लिए, हमें कैरेक्टर्स की 2-आयामी सरणी बनानी पड़ती थी। प्रत्येक पंक्

  1. - C++ प्रोग्राम: द्विघात समीकरण के सभी मूल खोजें

    परिचयएक द्विघात समीकरण ax² + bx + c के रूप में होता है। द्विघात समीकरण के मूल निम्न सूत्र द्वारा दिए जाते हैं - तीन मामले हैं - b² < 4*a*c - मूल वास्तविक नहीं हैं यानी वे कॉम्प्लेक्स हैं b² = 4*a*c - मूल वास्तविक हैं और दोनों मूल समान हैं 4*a*c - मूल वास्तविक हैं और दोनों मूल अलग हैं उदाहरण#incl