2진수 문자열, 즉 0과 1의 조합과 정수 값 k가 주어지고 주어진 k 1을 갖는 주어진 이진 문자열로 형성된 부분 문자열의 개수를 계산하는 것이 작업입니다.
입력 - 문자열 str ='10000100000', k =2
출력 − K개를 포함하는 이진 문자열의 부분 문자열 수는 − 6
설명 − 주어진 문자열에서 구성할 수 있는 부분 문자열은 1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010입니다. 따라서 정확히 2개의 1개를 갖는 6개의 부분 문자열이 있습니다.
입력 - 문자열 str ='10000100000', k =3
출력 − K개를 포함하는 이진 문자열의 부분 문자열 수는 − 0
설명 − k의 정수 값이 3으로 주어지며 이진수가 포함된 문자열을 확인하면 2개만 있습니다. 따라서 하위 문자열에 k개의 1이 주어질 가능성은 없습니다.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
0과 1의 조합과 정수 변수 k를 갖는 이진수 문자열을 입력하십시오.
-
length() 함수를 사용하여 문자열의 길이를 계산하고 추가 처리를 위해 데이터를 함수에 전달합니다.
-
k개의 하위 문자열을 저장하기 위해 임시 변수 count 및 total을 0으로 선언합니다.
-
크기의 1의 빈도를 string의 길이에 1을 더한 값으로 저장하는 배열을 선언하고 0으로 초기화하고 배열의 첫 번째 요소를 1로 설정합니다.
-
0부터 배열 길이까지 FOR 루프 시작
-
루프 내에서 total을 total + str[i] - '0'으로 설정합니다. IF total>=k를 확인한 다음 count를 count + arr[total-k]로 설정합니다.
-
반품 횟수
-
결과를 인쇄하십시오.
예시
#include <bits/stdc++.h>
using namespace std;
int sub_k_ones(string str, int length, int k){
int count = 0;
int total_1 = 0;
int arr_fre[length + 1] = {0};
arr_fre[0] = 1;
for (int i = 0; i < length; i++){
total_1 = total_1 + (str[i] - '0');
if (total_1 >= k){
count = count + arr_fre[total_1 - k];
}
arr_fre[total_1]++;
}
return count;
}
int main(){
string str = "10000100000";
int length = str.length();
int k = 2;
cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of substrings of a binary string containing K ones are: 6