C++で文字列に含まれるアナグラム部分文字列の総数を求める方法

入力として文字列 str[] が与えられます。この記事の目的は、str[] 内に存在するアナグラム部分文字列の総数を数えることです。2つの文字列が互いにアナグラムであるとは、含まれる文字の種類と出現回数が完全に一致していることを指します。文字の並び順は異なっていても構いません。

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

それでは、具体例を見てみましょう。

入力 − str[] = "abccb"

出力 − アナグラム部分文字列の総数 − 4

説明 − アナグラムとなる組み合わせは (b,b)、(c,c)、(bc,cb)、(bcc,ccb) の4つです。

入力 − str = "aaa"

出力 − アナグラム部分文字列の総数 − 4

説明 − アナグラムとなる組み合わせは (a,a)、(a,a)、(a,a)、(aa,aa) の4つです。

プログラムで使用するアプローチ

ここでは、英字26文字の出現頻度ベクトルと、その頻度を持つ部分文字列の個数を格納するマップを利用します。map<vector<int>, int> mp_vec; のうち、vector<int> vec(MAX, 0) には現在注目している部分文字列に含まれる各アルファベットの出現回数が保存され、マップの値には同じ頻度ベクトルを持つ部分文字列の個数が記録されます。あるアナグラムグループに属する部分文字列の個数が x である場合、そこから作れるアナグラムペアの総数は x*(x-1)/2 となります。

• 文字列 str[] を文字配列として受け取ります。

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

• カウント用変数 count を 0 で初期化します。

• マップ map<vector<int>, int> mp_vec; を用意します。

• 2重の for ループ(i=0 から i<length、j=i から j<length)で str[] を走査します。

• 各部分文字列 str[i〜j] に対して、vector<int> vec(MAX, 0); が含まれる英字の出現回数を保持します。

• 現在の文字 c を str[j] として取得し、temp=c-'a' によって整数値に変換します。

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

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

• 続いて、すべての頻度ベクトルを格納したマップを、イテレータ it=mp_vec.begin() から it != mp_vec.end() までの for ループで走査し、集計を行います。

• 各カウント it->second に対して ((last) * (last-1))/2 を count に加算することで、すべてのアナグラムペアを計上します。

• 最終的に、すべてのアナグラムの総数が得られます。

• count を結果として返します。

実装例

#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