แนวคิด
ในส่วนที่เกี่ยวกับสตริงที่เข้ารหัสที่กำหนด ซึ่งการทำซ้ำของสตริงย่อยจะถูกระบุเป็นสตริงย่อยตามด้วยจำนวนสตริงย่อย ตัวอย่างเช่น หากสตริงที่เข้ารหัสคือ “pq2rs2” และ k=5 ดังนั้นเอาต์พุตจะเป็น 'r' เนื่องจากสตริงที่ถอดรหัสคือ "pqpqrs" และอักขระตัวที่ 5 คือ 'r'
ควรสังเกตว่าความถี่ของสตริงย่อยที่เข้ารหัสสามารถมีได้มากกว่าหนึ่งหลัก ตัวอย่างเช่น ใน “pq12r3” pq จะถูกทำซ้ำ 12 ครั้ง ที่นี่ไม่มี 0 นำหน้าในความถี่ของสตริงย่อย
อินพุต
"p2q2r3", k = 6
ผลลัพธ์
r
สตริงที่ถอดรหัสคือ "ppqqrrr"
อินพุต
"pq4r2ts3", k = 11
ผลลัพธ์
t
สตริงที่ถอดรหัสคือ "pqpqpqpqrrtststs"
วิธีการ
ในที่นี้ อัลกอริทึมแบบขั้นตอนคือ −
- กำหนดความยาวของสตริงย่อยปัจจุบัน ใช้ตัวชี้สองตัว เราต้องแก้ไขตัวชี้หนึ่งตัวที่จุดเริ่มต้นของสตริงย่อยและดำเนินการตัวชี้อีกตัวหนึ่งจนกว่าจะไม่พบตัวเลข
- กำหนดความถี่ของการทำซ้ำโดยเลื่อนตัวชี้ที่สองต่อไปจนกว่าจะไม่พบตัวอักษร
- กำหนดความยาวของสตริงย่อยหากมีการทำซ้ำโดยการคูณความถี่และความยาวเดิม
-
มีการสังเกตว่าหากความยาวนี้น้อยกว่า k อักขระที่ต้องการจะอยู่ในสตริงย่อยที่ตามมา เราต้องลบความยาวนี้ออกจาก k เพื่อรักษาจำนวนอักขระที่ต้องครอบคลุม
-
จะเห็นได้ว่าหากความยาวน้อยกว่าหรือเท่ากับ k อักขระที่ต้องการจะอยู่ในสตริงย่อยปัจจุบัน เนื่องจาก k ถูกสร้างดัชนี 1 ตัว ให้ลดมันลง 1 แล้วจึงนำ mod ที่มีความยาวสตริงย่อยเดิมมาใช้ ในที่นี้ อักขระที่ต้องการคืออักขระที่ k จากจุดเริ่มต้นของสตริงย่อยซึ่งชี้โดยตัวชี้ตัวแรก
ตัวอย่าง
// 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
