復号化された文字列のk番目の文字を検索します-C++で–2を設定します

コンセプト

サブストリングの繰り返しがサブストリングとそれに続くサブストリングのカウントとして示される、特定のエンコードされたストリングに関して。したがって、たとえば、暗号化された文字列が「pq2rs2」でk =5の場合、復号化された文字列は「pqpqrsrs」であり、5番目の文字は「r」であるため、出力は「r」になります。

暗号化された部分文字列の頻度は1桁を超える場合があることに注意してください。したがって、たとえば「pq12r3」では、pqが12回繰り返されます。ここでは、サブストリングの頻度に先行0は存在しません。

入力

"p2q2r3", k = 6

出力

r

復号化された文字列は「ppqqrrr」です

入力

"pq4r2ts3", k = 11

出力

t

復号化された文字列は「pqpqpqpqrrtststs」です

メソッド

ここで、段階的アルゴリズムは-

• 現在の部分文字列の長さを決定します。 2つのポインターを実装します。サブストリングの開始時に1つのポインターを修正し、数字が見つからなくなるまで別のポインターを続行する必要があります。
• アルファベットが見つからなくなるまで2番目のポインタをさらに移動して、繰り返しの頻度を決定します。
• 頻度と元の長さを掛けて、部分文字列が繰り返される場合は、部分文字列の長さを決定します。

• この長さが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