【C++】2つの文字列を比較して共通しない文字を抽出するプログラム

この記事では、2つの異なる文字列を比較した際に、共通しない文字(どちらか一方にしか存在しない文字)を見つけ出すプログラムについて解説します。

ご存知の通り、文字列とは本質的に文字の配列です。そのため、比較を行う際は、一方の文字列の文字を先頭から順に走査しながら、その文字がもう一方の文字列にも存在するかどうかを確認していきます。

ここで、最初の文字列をA、2番目の文字列をBとすると、まず「A − B」(Aには含まれるがBには含まれない文字)が求められます。同様の手順で「B − A」も計算できます。

この2つの結果を組み合わせると、次の式になります。

( A − B ) ∪ ( B − A )

つまり、これは両方の文字列全体の中で共通しない要素(差集合の和集合)を表しています。

サンプルコード

#include <iostream>
using namespace std;
int main() {
    int len1 = 5, len2 = 4;
    char str1[len1] = "afbde", str2[len2] = "wabq";
    cout << "Uncommon Elements :" << endl;
    // str1 - str2 を求めるループ
    for(int i = 0; i < len1; i++) {
        for(int j = 0; j < len2; j++) {
            if(str1[i] == str2[j])
                break;
            // 文字列の末尾まで到達した場合
            else if(j == len2-1) {
                cout << str1[i] << endl;
                break;
            }
        }
    }
    // str2 - str1 を求めるループ
    for(int i = 0; i < len2; i++) {
        for(int j = 0; j < len1; j++) {
            if(str2[i] == str1[j])
                break;
            else if(j == len1-1) {
                cout << str2[i] << endl;
                break;
            }
        }
    }
    return 0;
}

実行結果

Uncommon Elements :
f
d
e
w
q

コードの解説

このプログラムでは、二重ループを用いて文字同士を照合しています。外側のループで注目している文字が、内側のループでもう一方の文字列内に存在するかどうかを1文字ずつチェックします。一致する文字が見つかった時点で、その文字は共通文字なので内側のループを抜けて出力は行いません。

一方、内側のループが文字列の末尾まで到達しても一致する文字が見つからなかった場合(j が文字列長 − 1 になったとき)、その文字は共通しない文字と判断され、出力されます。前半のループで「str1 − str2」を、後半のループで「str2 − str1」を求めることで、両方の文字列の共通しない文字をすべて抽出できる仕組みです。

計算量と注意点

この手法の時間計算量は O(n × m)(n、m はそれぞれの文字列の長さ)です。文字列が短いうちは問題ありませんが、文字数が多くなると処理が遅くなります。そのような場合は、std::set や std::unordered_set などのコンテナを利用することで、O(n + m) まで高速化可能です。また、同じ文字が文字列内に重複して登場する場合は重複して出力される点にも留意してください。