C++で2つの文字列に共通する文字ペアを数える方法

本記事では、2つの文字列(str1とstr2)が与えられたときに、両者に共通する文字のペア数を求める方法を解説します。具体的には、str1[i] == str2[j]となる組み合わせを「一致するペア」とみなし、該当するたびにカウントを1ずつ増やしていきます。逆にstr1[i] != str2[j]の場合はペアとして扱われず、カウントも増加しません。

実行例

入力 − str1 = "hello"
　　　 str2 = "heoo"
出力 − count is: 3

説明: str1[0] = str2[0](h)、str1[1] = str2[1](e)は一致しており、str1[2] != str2[2](l と o)は不一致です。さらにstr1[3] = str2[3](o)は一致しています。このように、同じ文字で構成されるペアは3組、異なる文字からなるペアは1組となります。

入力 − str1 = "point"
　　　 str2 = "print"
出力 − count is: 4

説明: str1[0] = str2[0](p)、str1[2] = str2[2](i)、str1[3] = str2[3](n)、str1[4] = str2[4](t)は一致しています。不一致なのはstr1[1] != str2[1](o と r)のみです。したがって、一致するペアは4組、不一致のペアは1組となります。

プログラムで採用しているアプローチ

• 2つの文字列str1とstr2を入力として受け取ります。
• length()関数を使って両方の文字列の長さ(スペースを含む文字数)を整数値として取得します。
• まず、両方の文字列における各文字の出現頻度を0で初期化します。
• str1の頻度を更新するには「f1[str1[i] - 'a']++」を適用し、反復処理のたびに該当文字の頻度を1ずつ増やします。str2についても同じ処理を行います。
• ペア数を算出する際は、f1とf2の対応する各要素に対してmin()関数を適用します。
• 最後に結果を出力します。

サンプルコード

#include <iostream>
using namespace std;
// 有効なインデックスペアを数える関数
int pairs(string str1, int size1, string str2, int size2){
   // 文字列str1とstr2の文字出現頻度を格納する配列 f1 と f2
   int f1[26] = { 0 };
   int f2[26] = { 0 };
   // 変数cは有効なペアの数を数えるために使用
   int i, c = 0;
   // str1とstr2の出現頻度を更新
   for (i = 0; i < size1; i++){
      f1[str1[i] - 'a']++;
   }
   for (i = 0; i < size2; i++){
      f2[str2[i] - 'a']++;
   }
   // 有効なペアの数を求める
   for (i = 0; i < 26; i++){
      c += (min(f1[i], f2[i]));
   }
   return c;
}
// main関数
int main(){
   string str1 = "tutorialspoint", str2 = "codingground";
   int size1 = str1.length(), size2 = str2.length();
   cout<<"Total pairs with str1[i]=str2[j] are: ";
   cout << pairs(str1, size1, str2, size2);
   return 0;
}

出力結果

上記のコードを実行すると、以下のような出力が得られます。

Total pairs with str1[i]=str2[j] are − 6

計算量について

このアルゴリズムの時間計算量はO(n + m)(n、mはそれぞれの文字列の長さ)であり、空間計算量はO(1)です。26個分のアルファベット頻度配列のみを使用するため、文字列が長くなっても非常に効率よく動作します。二重ループで全ペアを総当たり的に比較する方法(O(n × m))と比べても、大幅に高速である点が大きなメリットです。