컨셉
부분 문자열의 반복이 부분 문자열 뒤에 오는 부분 문자열로 표시되는 인코딩된 문자열과 관련하여. 예를 들어 암호화된 문자열이 "pq2rs2"이고 k=5인 경우 복호화된 문자열이 "pqpqrsrs"이고 5번째 문자가 'r'이므로 출력은 '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