सी ++ में लक्ष्य के समान अद्वितीय बाद की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो लोअरकेस स्ट्रिंग्स s और t हैं, हमें s के बाद के क्रमों की संख्या ज्ञात करनी है जो t के बराबर हैं। अगर उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 तक लौटाएं।

इसलिए, यदि इनपुट s ="abbd" t ="bd" जैसा है, तो आउटपुट 2 होगा, क्योंकि दो संभावित परिणाम "bd" हैं।

s[1] कॉनटेनेट s[3]
एस[2] एस [3] को संयोजित करें।

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

मी :=10^9 + 7
यदि t का आकार 0 के समान है, तो -
- वापसी 0
यदि t, s के समान है, तो -
- वापसी 1
यदि t का आकार> s का आकार, तो -
- वापसी 0
आकार की एक सरणी तालिका को t + 1 के आकार के समान परिभाषित करें और 0 से भरें
टेबल [0] :=1
इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -
- एक सरणी को ऑनसेव परिभाषित करें:=तालिका
- इनिशियलाइज़ j :=0 के लिए, जब j <टेबल का आकार, अपडेट करें (j को 1 से बढ़ाएँ), करें -
  - यदि s[i] t[j] के समान है, तो -
    - टेबल [जे + 1] =(टेबल [जे + 1] मॉड एम + ऑनसेव [जे] मॉड एम)
टेबल [जे + 1] =(टेबल [जे + 1] मॉड एम + ऑनसेव [जे] मॉड एम)

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

उदाहरण

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