ধারণা
একটি প্রদত্ত এনকোড করা স্ট্রিংয়ের ক্ষেত্রে যেখানে সাবস্ট্রিংগুলির পুনরাবৃত্তিগুলিকে সাবস্ট্রিং হিসাবে নির্দেশ করা হয় এবং সাবস্ট্রিংগুলির গণনা দ্বারা অনুসরণ করা হয়৷ সুতরাং, উদাহরণস্বরূপ, যদি এনক্রিপ্ট করা স্ট্রিং হয় "pq2rs2" এবং k=5, তাহলে আউটপুট হবে 'r' কারণ ডিক্রিপ্ট করা স্ট্রিং হল "pqpqrsrs" এবং 5ম অক্ষর হল 'r'৷
এটি লক্ষ করা উচিত যে এনক্রিপ্ট করা সাবস্ট্রিংয়ের ফ্রিকোয়েন্সি এক সংখ্যার বেশি হতে পারে। সুতরাং, উদাহরণস্বরূপ, "pq12r3" এ, pq 12 বার পুনরাবৃত্তি হয়। এখানে, সাবস্ট্রিং এর ফ্রিকোয়েন্সিতে কোন লিডিং 0 উপস্থিত নেই।
ইনপুট
"p2q2r3", k = 6
আউটপুট
r
ডিক্রিপ্ট করা স্ট্রিং হল "ppqqrrr"
ইনপুট
"pq4r2ts3", k = 11
আউটপুট
t
ডিক্রিপ্ট করা স্ট্রিং হল "pqpqpqpqrrtsstst"
পদ্ধতি
এখানে, ধাপে ধাপে অ্যালগরিদম হল −
- কারেন্ট সাবস্ট্রিং এর দৈর্ঘ্য নির্ধারণ করুন। দুটি পয়েন্টার প্রয়োগ করুন। সাবস্ট্রিং শুরু করার সময় আমাদের একটি পয়েন্টার ঠিক করতে হবে এবং একটি সংখ্যা না পাওয়া পর্যন্ত অন্য পয়েন্টারকে এগিয়ে যেতে হবে।
- একটি বর্ণমালা পাওয়া না যাওয়া পর্যন্ত দ্বিতীয় পয়েন্টারকে আরও সরানোর মাধ্যমে পুনরাবৃত্তির ফ্রিকোয়েন্সি নির্ধারণ করুন।
- সাবস্ট্রিং এর দৈর্ঘ্য নির্ধারণ করুন যদি এটি পুনরাবৃত্তি হয় ফ্রিকোয়েন্সি এবং এর মূল দৈর্ঘ্য গুণ করে।
-
এটি লক্ষ্য করা গেছে যে এই দৈর্ঘ্যটি k এর থেকে ছোট হলে প্রয়োজনীয় অক্ষরটি নিম্নলিখিত সাবস্ট্রিং-এ থাকে। কভার করার জন্য প্রয়োজনীয় অক্ষরের সংখ্যার গণনা বজায় রাখতে আমাদের k থেকে এই দৈর্ঘ্য বিয়োগ করতে হবে।
-
এটা দেখা গেছে যে যদি দৈর্ঘ্য k এর থেকে ছোট বা সমান হয়, তাহলে প্রয়োজনীয় অক্ষর বর্তমান সাবস্ট্রিং-এ থাকে। কারণ k 1-সূচীযুক্ত, এটিকে 1 দ্বারা হ্রাস করুন এবং তারপর মূল সাবস্ট্রিং দৈর্ঘ্য সহ এটির মোড নিন। এখানে, প্রয়োজনীয় অক্ষর হল সাবস্ট্রিং এর শুরু থেকে kth অক্ষর যা প্রথম পয়েন্টার দ্বারা নির্দেশিত।
উদাহরণ
// C++ program to find K'th character in
// decrypted string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find K'th character in
// Encoded String
char encodedChar(string str, int k){
int a, b;
int m = str.length();
// Used to store length of substring
int len1;
// Used to store length of substring when
// it is repeated
int num1;
// Used to store frequency of substring
int freq1;
a = 0;
while (a < m) {
b = a;
len1 = 0;
freq1 = 0;
// Determine length of substring by
// traversing the string until
// no digit is found.
while (b < m && isalpha(str[b])) {
b++;
len1++;
}
// Determine frequency of preceding substring.
while (b < m && isdigit(str[b])) {
freq1 = freq1 * 10 + (str[b] - '0');
b++;
}
// Determine length of substring when
// it is repeated.
num1 = freq1 * len1;
// It has been seen that if length of repeated substring is
less than // k then required character is present in next
// substring. Subtract length of repeated
// substring from k to keep account of number of
// characters required to be visited.
if (k > num1) {
k -= num1;
a = b;
}
// It has been seen that if length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else {
k--;
k %= len1;
return str[a + k];
}
}
// This is for the case when there
// are no repetition in string.
// e.g. str="abced".
return str[k - 1];
}
// Driver Code
int main(){
string str1 = "pqpqpqpqrrtststs";
int k1 = 11;
cout << encodedChar(str1, k1) << endl;
string str2 = "p2q2r3";
int k2 = 6;
cout << encodedChar(str2, k2) << endl;
return 0;
} আউটপুট
t r
