C++의 총 아나그램 부분 문자열 수

<시간/>

문자열 str[]이 입력으로 주어집니다. 목표는 str[]에 있는 아나그램 부분 문자열의 수를 계산하는 것입니다. 두 문자열이 같은 수의 문자를 포함하고 모든 문자가 둘 다에 있는 경우 두 문자열은 서로의 아나그램입니다. 캐릭터의 순서는 다를 수 있습니다.

"abc"는 "cba", "bca" 등의 아나그램입니다.

예를 들어 이해합시다.

입력 - str[] ="abccb"

출력 − 총 아나그램 부분 문자열의 개수는 − 4입니다.

설명 − 아나그램은 − (b,b), (c,c), (bc,cb), (bcc,ccb)

입력 - str ="아아아"

출력 − 총 아나그램 부분 문자열의 개수는 − 4입니다.

설명 − 아나그램은 − (a,a), (a,a), (a,a), (aa,aa)

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

우리는 부분 문자열에 영어 알파벳의 빈도와 배열에 있는 그러한 부분 문자열의 개수가 있는 벡터를 포함하는 맵을 가져오고 있습니다. 지도, int> mp_vec; vector vec(MAX, 0)은 현재 하위 문자열에 있는 26개 알파벳의 빈도를 모두 저장합니다. 그리고 매핑된 정수는 동일한 빈도 벡터를 가진 이러한 부분 문자열의 개수입니다. 아나그램의 경우 count가 x인 경우 각 부분 문자열에 대해. 그러면 총 아나그램 쌍은 x*(x-1)/2가 됩니다.

문자열 str[]을 문자 배열로 사용합니다.
anagram_substring(string str, int length) 함수는 문자열을 가져와서 전체 anagram 부분 문자열의 개수를 반환합니다.
초기 카운트를 0으로 합니다.
지도 가져오기, map, int> mp_vec;
i=0에서 i까지 2개의 for 루프를 사용하여 str[] 순회
각 부분 문자열 str[i to j]에 대해. 벡터 vec(최대, 0); 여기에는 영어 알파벳 수가 포함됩니다.
c의 현재 문자를 str[j]로 가져옵니다. temp=c-'a'로 정수 값을 가져옵니다.
vec[temp]++로 빈도를 업데이트합니다.
mp_vec[vec]++를 사용하여 이 주파수 벡터에 해당하는 개수를 늘립니다.
이제 it=mp_vec.begin() 반복자에서 !=mp_vec.end()까지 for 루프를 사용하여 모든 빈도 벡터와 집계 부분 문자열 수를 포함하는 맵을 탐색합니다.
it->second로 계산할 때마다 ((last) * (last-1))/2를 추가하여 모든 아나그램 쌍을 계산합니다.
마지막에 우리는 모든 아나그램의 개수를 갖게 될 것입니다.
결과로 카운트를 반환합니다.

예

#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int anagram_substring(string str, int length){
   int count = 0;
   map<vector<int>, int> mp_vec;
   for (int i=0; i<length; i++){
      vector<int> vec(MAX, 0);
      for (int j=i; j<length; j++){
         char c = str[j];
         char temp = c - 'a';
         vec[temp]++;
         mp_vec[vec]++;
      }
   }
   for (auto it = mp_vec.begin(); it != mp_vec.end(); it++){
      int last = it->second;
      count += ((last) * (last-1))/2;
   }
   return count;
}
int main(){
   string str = "TP";
   int length = str.length();
   cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
   return 0;
}

출력

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

Count of total anagram substrings are: 3