अवधारणा
किसी दिए गए एन्कोडेड स्ट्रिंग के संबंध में जहां सबस्ट्रिंग के दोहराव को सबस्ट्रिंग के रूप में दर्शाया जाता है और उसके बाद सबस्ट्रिंग की गिनती होती है। इसलिए, उदाहरण के लिए, यदि एन्क्रिप्टेड स्ट्रिंग "pq2rs2" और k=5 है, तो आउटपुट 'r' होगा क्योंकि डिक्रिप्टेड स्ट्रिंग "pqpqrsrs" है और 5वां वर्ण 'r' है।
यह ध्यान दिया जाना चाहिए कि एन्क्रिप्टेड सबस्ट्रिंग की आवृत्ति एक से अधिक अंकों की हो सकती है। इसलिए, उदाहरण के लिए, "pq12r3" में, pq को 12 बार दोहराया जाता है। यहां, सबस्ट्रिंग की आवृत्ति में कोई अग्रणी 0 मौजूद नहीं है।
इनपुट
"p2q2r3", k = 6
आउटपुट
r
डिक्रिप्टेड स्ट्रिंग "ppqqrrr" है
इनपुट
"pq4r2ts3", k = 11
आउटपुट
t
डिक्रिप्टेड स्ट्रिंग "pqpqpqpqrrtststs" है
विधि
यहाँ, स्टेप वाइज एल्गोरिथम है -
- वर्तमान सबस्ट्रिंग की लंबाई निर्धारित करें। दो पॉइंटर्स लागू करें। हमें सबस्ट्रिंग की शुरुआत में एक पॉइंटर को ठीक करना होगा और एक अंक न मिलने तक दूसरे पॉइंटर को आगे बढ़ाना होगा।
- जब तक कोई अक्षर नहीं मिलता तब तक दूसरे पॉइंटर को आगे बढ़ाते हुए दोहराव की आवृत्ति निर्धारित करें।
- सबस्ट्रिंग की लंबाई निर्धारित करें यदि इसे आवृत्ति और इसकी मूल लंबाई को गुणा करके दोहराया जाता है।
-
यह देखा गया है कि यदि यह लंबाई 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