แนวคิด
เมื่อได้รับ encoded string ที่การซ้ำของ substring ถูกบ่งชี้โดย substring ตามด้วยจำนวนของ substring ดังนั้น เช่น ถ้า encrypted string คือ “pq2rs2” และ k=5 output จะเป็น ‘r’ เพราะ decrypted string คือ “pqpqrsrs” และตัวอักษรที่ 5 คือ ‘r’
ควรสังเกตว่า frequency ของ encrypted substring อาจมีมากกว่าหนึ่งหลัก ดังนั้น เช่น ใน “pq12r3” pq จะถูกซ้ำ 12 ครั้ง ที่นี่ ไม่มี leading 0 ใน frequency ของ substring
อินพุต
"p2q2r3", k = 6
เอาต์พุต
r
Decrypted string คือ "ppqqrrr"
อินพุต
"pq4r2ts3", k = 11
เอาต์พุต
t
Decrypted string คือ "pqpqpqpqrrtststs"
วิธีการ
ที่นี่ อัลกอริทึมแบบทีละขั้นตอนคือ −
- หาความยาวของ current substring ใช้ two pointers เราต้อง fix หนึ่ง pointer ที่ต้นของ substring และเลื่อนอีก pointer จนกว่าจะไม่พบ digit
- หา frequency ของการซ้ำโดยการเลื่อน second pointer ต่อจนกว่าจะไม่พบ alphabet
- หาความยาวของ substring ถ้าถูกซ้ำโดยการคูณ frequency กับความยาวเดิม
สังเกตได้ว่าถ้าความยาวนี้น้อยกว่า k ตัวอักษรที่ต้องการอยู่ใน substring ถัดไป เราต้องลบความยาวนี้ออกจาก k เพื่อนับจำนวนตัวอักษรที่ต้องครอบคลุม
พบว่าถ้าความยาวนี้น้อยกว่าหรือเท่ากับ k ตัวอักษรที่ต้องการอยู่ใน current substring เนื่องจาก k เป็น 1-indexed ให้ลดลง 1 แล้วเอา mod กับความยาว substring เดิม ตัวอักษรที่ต้องการคือตัวอักษรที่ k จากต้นของ substring ที่ชี้โดย first pointer
ตัวอย่างโค้ด
// โปรแกรม C++ เพื่อหา K'th character ใน // decrypted string #include <bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการหา K'th character ใน // Encoded String char encodedChar(string str, int k){ int a, b; int m = str.length(); // ใช้เก็บความยาวของ substring int len1; // ใช้เก็บความยาวของ substring เมื่อ // ถูกซ้ำ int num1; // ใช้เก็บ frequency ของ substring int freq1; a = 0; while (a < m) { b = a; len1 = 0; freq1 = 0; // หาความยาวของ substring โดย // traverse string จนกว่า // จะไม่พบ digit while (b < m && isalpha(str[b])) { b++; len1++; } // หา frequency ของ substring ก่อนหน้า while (b < m && isdigit(str[b])) { freq1 = freq1 * 10 + (str[b] - '0'); b++; } // หาความยาวของ substring เมื่อ // ถูกซ้ำ num1 = freq1 * len1; // พบว่าถ้าความยาวของ repeated substring น้อยกว่า // k แล้ว required character อยู่ใน next // substring ลบความยาวของ repeated // substring จาก k เพื่อนับจำนวน // ตัวอักษรที่ต้องเยี่ยมชม if (k > num1) { k -= num1; a = b; } // พบว่าถ้าความยาวของ repeated substring มากกว่าหรือเท่ากับ k แล้ว // required character อยู่ใน current substring else { k--; k %= len1; return str[a + k]; } } // นี่สำหรับกรณีที่ไม่มี // การซ้ำใน string // เช่น 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
