문자열 str[]과 문자 X가 제공됩니다. 목표는 모든 하위 문자열에 X가 한 번 이상 포함되도록 str[]의 하위 문자열을 찾는 것입니다. str[]="abc '' 및 X='a'의 경우 'a'를 적어도 한 번 포함하는 하위 문자열은 "a", "ab", "abc"입니다. 카운트는 3입니다.
예를 들어 이해합시다.
입력 - str[] ="aabccd" X='c'
출력 − 문자 X를 한 번 이상 포함하는 하위 문자열의 수는 − 14
입니다.설명 - 적어도 하나의 'c'를 포함하는 부분 문자열은 "c", "c", "bc", "cc", "cd", "abc", "bcc", "ccd", "aabc", " abcc", "bccd", "aabcc", "abccd", "aabccd".
입력 − str[] ="설정" X='
출력 − 문자 X를 한 번 이상 포함하는 하위 문자열의 수는 − 14
입니다.설명 − 부분 문자열에는 "s", "s", "se", "gs", "set", "ngs", "set", "ings", "setti", " 팅", "세팅", "팅", "설정", "설정", "설정"
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 n개의 문자가 있는 string의 총 부분 문자열 수가 n*(n+1)/2라는 것을 알고 있습니다.
이제 문자열을 탐색하고 문자 X 앞의 문자를 임시로 계산합니다. X를 만나자마자 X를 포함하는 문자열의 길이는 temp+1이 됩니다. 이제 X를 포함하는 X개의 하위 문자열이 나머지 문자(길이-현재 인덱스) X( temp+1)가 됩니다. 이것을 추가하여 계산합니다. 이제 temp=0을 업데이트하고 문자열 끝까지 다음 X를 진행합니다. 마지막에 문자 X를 한 번 이상 포함하는 하위 문자열의 수로 count가 있습니다.
-
문자열 str과 문자 x를 가져옵니다.
-
함수 sub_x(char str[],int length,char x)는 문자열, 길이, 문자 x를 취하여 문자 x를 적어도 한 번 포함하는 부분 문자열의 개수를 반환합니다.
-
초기 카운트를 0으로 취합니다. str[]에서 첫 x 이전의 문자로 temp를 초기에 0으로 취합니다.
-
str[]의 가능한 모든 하위 문자열의 수에 대해 초기 개수 크기*(size+1)/2를 취합니다.
-
i=0에서 i
-
str[i]가 x가 아니면 첫 x 이전의 문자로 temp를 증가시킵니다.
-
str[i] ==x이면 x를 포함한 문자열의 길이는 temp+1이 됩니다. str[]의 나머지 문자는 length-i입니다.
-
모든 하위 문자열은 ( temp+1) * (length-i)입니다. 이것을 추가하여 계산합니다. 이제 다음 반복을 위해 temp=0을 업데이트하십시오.
-
str[] 끝에 도달할 때까지 이 작업을 수행합니다.
-
마지막에 결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
int count = 0;
int temp = 0;
for (int i = 0; i < length; i++){
if (str[i] == x){
int temp_2 = temp + 1;
count = count + temp_2 * (length - i);
temp = 0;
}
else{
temp++;
}
}
return count;
}
int main(){
string str = "abcabbc";
int length = str.length();
char x = 'a';
cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of sub-strings that contain character X at least once are: 19