C++で一方の文字列の部分文字列がもう一方の文字列にいくつ含まれるかを調べる方法

この記事では、2つの文字列が与えられたとき、1つ目の文字列の部分文字列のうち、2つ目の文字列内に存在するものがいくつあるかを求める方法を解説します。なお、同じ部分文字列が複数回出現する場合は、その回数もカウント対象となります。

具体例

入力 : string1 = "fogl"
       string2 = "google"
出力 : 6
説明 : string2 内に存在する string1 の部分文字列は
       [ "o", "g", "l", "og", "gl", "ogl" ] の6個です。

入力 : string1 = "ajva"
       string2 = "java"
出力 : 5
説明 : string2 内に存在する string1 の部分文字列は
       [ "a", "j", "v", "a", "va" ] の5個です。

解決へのアプローチ

例を見ると分かるように、まず1つ目の文字列から取り得るすべての部分文字列を生成し、その各部分文字列が2つ目の文字列内に存在するかどうかを順番にチェックしていきます。存在していればカウンターを1つ増やし、すべての部分文字列の確認が終わった時点で、カウンターに格納された値が答えとなります。

この方法の計算量は O(n² × m) です(n は string1 の長さ、m は string2 の長さ)。部分文字列の生成に O(n²)、それぞれの検索に find 関数による O(m) を要するためです。より高速化が必要な場合は、接尾辞配列やハッシュセットを活用する手法もありますが、まずはシンプルな実装を理解しましょう。

C++での実装コード

以下が、上記のアプローチを実装したC++のコードです。

サンプルコード

#include<iostream>
#include<string>
using namespace std;

int main() {
    string str1 = "ajva";
    string str2 = "java";
    int count = 0; // 結果を格納するカウンター
    int n = str1.length();

    for (int i = 0; i < n; i++) {

        // str1 のすべての部分文字列を格納するための変数
        string str3;
        for (int j = i; j < n; j++) {
            str3 += str1[j];

            // 部分文字列がもう一方の文字列に存在するかどうかを判定
            if (str2.find(str3) != string::npos)
                count++;
        }
    }
    cout << "Number of substrings of one string present in other : " << count;
    return 0;
}

実行結果

Number of substrings of one string present in other : 5

コードの解説

まず、コード冒頭で2つの文字列に値を設定し、カウンターを0で初期化しています。次に、外側のループと内側のループを組み合わせて文字列全体を走査し、str1 から取り得るすべての部分文字列を str3 に格納していきます。そして、生成した各部分文字列が str2 内に存在するかどうかを find 関数で判定し、存在すればカウンターを1ずつ増加させます。最後に、カウンター変数に保存された値を出力として表示します。

ポイントは、str2.find(str3) が該当する部分文字列を見つけられなかった場合に string::npos を返すという仕様です。この戻り値と比較することで、部分文字列の有無を正確に判定できます。

まとめ

この記事では、ある文字列の部分文字列が別の文字列内にいくつ存在するかを求めるシンプルな解法を紹介しました。紹介したロジックは、C言語、Java、Pythonなど、他のプログラミング言語でも同様に実装することが可能です。本記事が皆さんの学習の一助となれば幸いです。