C++에서 첫 번째 문자와 마지막 문자가 동일한 부분 문자열 계산

<시간/>

문자열 str이 주어집니다. 목표는 동일한 시작 및 끝 문자를 가진 str의 부분 문자열 수를 계산하는 것입니다. 예를 들어 입력이 "baca"인 경우 하위 문자열은 "b", "a", "c", "a", "aca"가 됩니다. 총 5.

예를 들어 이해합시다.

입력 − str="abaefgf"

출력 −첫 번째와 마지막 문자가 같은 부분 문자열의 개수는 다음과 같습니다. 9

설명 − 하위 문자열은 다음과 같습니다.

“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.

입력 - str="abcdef"

출력 −첫 번째와 마지막 문자가 같은 부분 문자열의 개수는 다음과 같습니다. 6

설명 − 하위 문자열은 −

“a” , “b” , “c”, “d”, “e” ,”f”. Total 6

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

주어진 문제를 해결하기 위한 여러 가지 접근 방식, 즉 순진한 접근 방식과 효율적인 접근 방식이 있을 수 있습니다. 그럼 먼저 순진한 접근 방식을 살펴보겠습니다. 모든 길이의 부분 문자열을 check() 함수에 전달할 것입니다. 해당 하위 문자열이 동일한 문자로 시작하고 끝나는 경우 개수를 증가시킵니다.

문자열 str을 가져옵니다. 길이를 str.size()로 계산합니다.
check(string str) 함수는 부분 문자열 str을 취하여 첫 번째 문자와 마지막 문자가 동일한지 확인합니다. ( str[0]==str[길이-1] ). 참이면 1을 반환합니다.
함수 check_Start_End(string str, int length)는 str과 그 길이를 입력으로 받아 같은 문자로 시작하고 끝나는 str의 부분 문자열 개수를 반환합니다.
초기 카운트를 0으로 합니다.
두 개의 for 루프를 사용하여 str을 탐색합니다. i=0에서 i<길이 및 내부 j=1에서 j=length-1까지.
모든 길이의 substr(i,j)를 사용하여 모든 부분 문자열을 얻습니다. 각 부분 문자열을 check()에 전달하십시오. 1을 반환하면 count를 증가시킵니다.
두 for 루프의 끝에서 count는 동일한 시작 및 끝 문자를 가진 str의 여러 부분 문자열을 갖습니다.
원하는 결과로 카운트를 반환합니다.

효율적인 접근

보시다시피, 그 대답은 원래 문자열의 각 문자의 빈도에 따라 다릅니다.

예를 들어 "bacba"에서 "b"의 빈도는 2이고 "b"를 포함하는 부분 문자열은 "b", "bacb" 및 "b"입니다.

2+1C2=3입니다. 먼저 각 문자의 빈도를 확인하고 ^{(char+1의 빈도)} 를 추가합니다. C₂ .

문자열 str을 가져옵니다. 길이를 str.size()로 계산합니다.
함수 check_Start_End(string str, int length)는 str과 그 길이를 입력으로 받아 같은 문자로 시작하고 끝나는 str의 부분 문자열 개수를 반환합니다.
초기 count-0을 취합니다.
배열 arr[26]을 사용하여 각 문자의 빈도를 저장합니다.
문자열을 탐색하고 주파수를 저장합니다. arr[str[i]='a']++.
주파수 배열 arr[26]을 트래버스하고 각 주파수 arr[i]에 대해 arr[i]*(arr[i]+1)/2를 추가합니다. 계산합니다.
결국 결과로 카운트를 반환합니다.

예(순진한 접근 방식)

#include <bits/stdc++.h>
using namespace std;
int check(string str){
   int length = str.length();
   if(str[0] == str[length-1]){
      return 1;
   }
}
int check_Start_End(string str, int length){
   int count = 0;
   for (int i = 0; i < length; i++){
      for (int j = 1; j <= length-i; j++){
         if (check(str.substr(i, j))){
            count++;
         }
      }
   }
   return count;
}
int main(){
   string str = "bcbdedfef";
   int length = str.length();
   cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of substrings with same first and last characters are: 13

예시(효율적인 접근)

#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
   int count = 0;
   int arr[maximum] = {0};
   for(int i=0; i<length; i++){
      arr[str[i] - 'a']++;
   }
   for (int i=0; i<maximum; i++){
      count = count + (arr[i]*(arr[i]+1)/2);
   }
   return count;
}
int main(){
   string str = "bcbdedfef";
   int length = str.length();
   cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str,
length);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of substrings with same first and last characters are: 13