Tìm ký tự thứ k của chuỗi được giải mã - Đặt - 2 trong C ++

Khái niệm

Đối với một chuỗi được mã hóa nhất định trong đó số lần lặp lại của các chuỗi con được biểu thị là chuỗi con theo sau là số chuỗi con. Vì vậy, ví dụ:nếu chuỗi được mã hóa là “pq2rs2” và k =5, thì đầu ra sẽ là ‘r’ vì chuỗi được giải mã là “pqpqrsrs” và ký tự thứ 5 là ‘r’.

Cần lưu ý rằng tần số của chuỗi con được mã hóa có thể có nhiều hơn một chữ số. Vì vậy, ví dụ, trong “pq12r3”, pq được lặp lại 12 lần. Ở đây, không có số 0 đứng đầu nào xuất hiện trong tần suất của chuỗi con.

Đầu vào

"p2q2r3", k = 6

Đầu ra

r

Chuỗi được giải mã là "ppqqrrr"

Đầu vào

"pq4r2ts3", k = 11

Đầu ra

t

Chuỗi được giải mã là "pqpqpqpqrrtststs"

Phương pháp

Ở đây, thuật toán từng bước là -

• Xác định độ dài của chuỗi con hiện tại. Triển khai hai con trỏ. Chúng tôi phải sửa một con trỏ khi bắt đầu chuỗi con và tiếp tục một con trỏ khác cho đến khi không tìm thấy chữ số.
• Xác định tần suất lặp lại bằng cách di chuyển con trỏ thứ hai xa hơn cho đến khi không tìm thấy bảng chữ cái.
• Xác định độ dài của chuỗi con nếu nó được lặp lại bằng cách nhân tần số với độ dài ban đầu của nó.

• Người ta quan sát thấy rằng nếu độ dài này nhỏ hơn k, thì ký tự bắt buộc nằm trong chuỗi con theo sau. Chúng ta phải trừ độ dài này cho k để duy trì số lượng ký tự được yêu cầu được bao phủ.

• Người ta đã thấy rằng nếu độ dài nhỏ hơn hoặc bằng k, thì ký tự bắt buộc nằm trong chuỗi con hiện tại. Vì k là 1-index, hãy giảm nó đi 1 và sau đó lấy mod của nó với độ dài chuỗi con ban đầu. Ở đây, ký tự bắt buộc là ký tự thứ k kể từ đầu chuỗi con được trỏ bởi con trỏ đầu tiên.

Ví dụ

// 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;
}

Đầu ra

t
r