सी ++ में दी गई शक्ति के साथ उप-स्ट्रिंग खोजें

इस समस्या में, हमें एक स्ट्रिंग str और एक पूर्णांक पाउ दिया जाता है। हमारा काम है दी गई शक्ति के साथ एक उप-स्ट्रिंग ढूंढना ।

हमें उस सबस्ट्रिंग को वापस करना होगा जिसकी शक्ति पॉ के बराबर है।

स्ट्रिंग की शक्ति इसके पात्रों की शक्तियों का योग है।

चरित्र की शक्ति:ए -> 1, बी -> 2, सी -> 3,...

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input : string = "programming" power = 49
Output : 'pro'

स्पष्टीकरण -

Power of matrix : pro,
power(p) = 16
power(p) = 18
power(p) = 15
Total = 16 + 18 + 15 = 49

समाधान दृष्टिकोण

समस्या का एक आसान समाधान नेस्टेड लूप का उपयोग कर रहा है। हम स्ट्रिंग के माध्यम से लूप करेंगे और एक आंतरिक लूप का उपयोग करके, हम सबस्ट्रिंग पाएंगे। प्रत्येक सबस्ट्रिंग के लिए, हम शक्ति की गणना करेंगे। और फिर जांचें कि क्या यह 'पाउ' के बराबर है, यदि हाँ तो सही है, अन्यथा झूठी वापसी करें।

समस्या को हल करने के लिए एक कुशल दृष्टिकोण बिजली को स्टोर करने के लिए मानचित्र का उपयोग करना है। हम सबस्ट्रिंग की शक्ति की गणना करेंगे और इसे मानचित्र पर संग्रहीत करेंगे। जांचें कि क्या मानचित्र में कोई मान मौजूद है जो शक्ति को आवश्यक शक्ति के बराबर बना सकता है। यदि हां, तो सत्य लौटाएं . वापसी झूठी जब स्ट्रिंग के सभी वर्णों को ट्रैवर्स किया जाता है और कोई मान मिलान शक्ति नहीं मिलती है।

एल्गोरिदम

• चरण 1 - स्ट्रिंग को पार करें और घात (कर्पपाउ) ज्ञात करें।

• चरण 2 - यदि मान, (currPow - pow) मानचित्र में मौजूद है या नहीं।

  • चरण 2.1 - यदि हां, तो प्रिंट करें -> सबस्ट्रिंग।

• चरण 3 - नक्शे में currPow का मान डालें।

• चरण 4 - यदि स्ट्रिंग के सभी वर्णों को ट्रैवर्स किया जाता है, तो प्रिंट करें -> 'संभव नहीं'।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
   int i;
   unordered_map<int , int > powerSS;
   int currPower = 0;
   int N = str.length();
   for (i = 0; i < N; i++) {
      currPower = currPower + (str[i] - 'a' + 1);
      if (currPower == power) {
         cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
         return;
      }
      if (powerSS.find(currPower - power) != powerSS.end()) {
         cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
         cout<<" has power "<<power; return;
      }
      powerSS[currPower] = i;
   }
   cout<<"No substring found!";
}
int main() {
   string str = "programming";
   int power = 49;
   findSubStringWithPower(str, power);
   return 0;
}

आउटपुट

Substring : pro has power 49