এই সমস্যায়, আমাদের একটি স্ট্রিং স্ট্র এবং একটি পূর্ণসংখ্যা পাওয়ার দেওয়া হয়েছে। আমাদের কাজ হল প্রদত্ত শক্তি সহ একটি সাব-স্ট্রিং খুঁজে পাওয়া .
আমাদের সেই সাবস্ট্রিং ফেরত দিতে হবে যার পাওয়ার সমান।
স্ট্রিং এর শক্তি এটির অক্ষরের শক্তির যোগফল।
অক্ষরের শক্তি:a -> 1, b -> 2, c -> 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 − স্ট্রিংটি অতিক্রম করুন এবং পাওয়ার (currPow) খুঁজুন।
-
ধাপ 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
