समस्या विवरण
मान लीजिए हमारे पास दो स्ट्रिंग्स 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
- लूप से बाहर निकलें
- यदि ns का सबस्ट्रिंग इंडेक्स (i + 1 - k) से अंत तक, e के सबस्ट्रिंग इंडेक्स 0 से k-1 के समान है:
- m := e का आकार
- i := 0 से आरंभ करें, जब i <= n, i को 1 से बढ़ाते हुए:
- j := 0 से आरंभ करें, जब j < m, j को 1 से बढ़ाते हुए:
- dp[i][j][0] := 0
- dp[i][j][1] := 0
- j := 0 से आरंभ करें, जब j < m, j को 1 से बढ़ाते हुए:
- 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])
- यदि k > s[i] - 'a' का ASCII:
- l के लिए रेंज (0, 1) में:
- k := 0 से आरंभ करें, जब k < 26, k को 1 से बढ़ाते हुए:
- j := 0 से आरंभ करें, जब j < e का आकार, j को 1 से बढ़ाते हुए:
- 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
- यदि s1[i] 'a' के समान नहीं है:
- i := s1 के आकार से आरंभ करें, जब i >= 0, i को 1 से घटाते हुए:
- 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