C++でのアナグラムサブストリングの総数

入力として文字列str[]が与えられます。目標は、str[]に存在するアナグラムサブストリングの数を数えることです。 2つの文字列が同じ数の文字を含み、すべての文字が両方に含まれている場合、2つの文字列は互いにアナグラムです。文字の順序は異なる場合があります。

「abc」は「cba」、「bca」などのアナグラムです。

例を挙げて理解しましょう。

入力 − str [] =“ abccb”

出力 −アナグラムサブストリングの総数は− 4

説明 −アナグラムは−（b、b）、（c、c）、（bc、cb）、（bcc、ccb）

入力 − str =“ aaa”

出力 −アナグラムサブストリングの総数は− 4

説明 −アナグラムは−（a、a）、（a、a）、（a、a）、（aa、aa）

以下のプログラムで使用されているアプローチは次のとおりです

私たちは、サブストリングに英語のアルファベットの頻度と配列にそのようなサブストリングの数を含むベクトルを含むマップを取っています。 map 、int> mp_vec; vector vec（MAX、0）は、26個のアルファベットすべての頻度を現在のサブストリングに格納します。そして、マップされた整数は、同じ周波数ベクトルを持つそのようなサブストリングのカウントになります。アナグラムのカウントがxの場合、各サブストリングに対して。その場合、アナグラムペアの合計はx *（x-1）/2になります。

• 文字列str[]を文字配列として使用します。

• 関数anagram_substring（string str、int length）は文字列を受け取り、アナグラム部分文字列の総数を返します。

• 初期カウントを0とします。

• 地図を取ります、map 、int> mp_vec;

• i=0からi

• 各部分文字列str[itoj]に対して。 vector vec（MAX、0）;その中に英語のアルファベットのカウントが含まれます。

• cの現在の文字をstr[j]として取ります。その整数値をtemp=c-’a’で取得します。

• vec[temp]++で頻度を更新します。

• mp_vec[vec]++を使用してこの頻度ベクトルに対応するカウントを増やします。

• ここで、イテレータit =mp_vec.begin（）からそれに！=mp_vec.end（）までのforループを使用して、すべての頻度ベクトルと集計サブストリングカウントを含むマップをトラバースします。

• カウントごとに->秒、（（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