मान लीजिए कि हमारे पास दो लोअरकेस स्ट्रिंग्स 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"
आउटपुट
2
