C++で指定した文字列から始まり・終わる異なる部分文字列の数を求める方法

はじめに

このチュートリアルでは、指定された文字列で始まり、別の指定された文字列で終わる部分文字列の総数を求めるプログラムをC++で作成します。

問題設定として、1つの文字列と2つの部分文字列(開始文字列と終了文字列)が与えられます。その2つの条件を両方とも満たす「異なる」部分文字列の個数を数えるのが目的です。まずは具体例を見てみましょう。

入出力例

入力

str = "getmesomecoffee"
start = "m"
end = "e"

出力

6

この例では、与えられた文字列の中に条件を満たす異なる部分文字列が合計6つ存在します。具体的には「me」「mesome」「mesomemecoffe」「mesomemecoffee」「mecoffe」「mecoffee」の6つです。

アルゴリズムの手順

問題を解くための手順は以下の通りです。

• 文字列を初期化します。

• 文字列全体を走査し、開始文字列および終了文字列が出現するインデックスを調べて、それぞれ別の配列に保存します。

• 重複しない部分文字列を管理するためのセット(set)を初期化します。

• 文字列を先頭から順に走査します。

  • 現在のインデックスが、事前に作成した配列における開始文字列の出現位置と一致しているか確認します。

  • 開始文字列の位置が見つかったら、終了文字列を探索します。

  • 終了文字列が見つかるまで、文字を変数へ順次追加していきます。

  • 終了文字列が見つかった時点で、部分文字列のカウントを1増やし、その部分文字列をセットに追加します。

  • 部分文字列を格納する変数をリセットします。

• 最後に部分文字列の個数を出力します。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int getSubstringsCount(string str, string start, string end) {
    int substrings_count = 0, str_length = str.size(), start_length = start.size(), end_length = end.size();
    int start_matches_index[str_length] = {0}, end_matches_index[str_length] = {0};
    for (int i = 0; i < str_length; i++) {
        if (str.substr(i, start_length) == start) {
            start_matches_index[i] = 1;
        }
        if (str.substr(i, end_length) == end) {
            end_matches_index[i] = 1;
        }
    }
    set<string> substrings;
    string current_substring = "";
    for (int i = 0; i < str_length; i++) {
        if (start_matches_index[i]) {
            for (int j = i; j < str_length; j++) {
                if (!end_matches_index[j]) {
                    current_substring += str[j];
                }
                if (end_matches_index[j]) {
                    current_substring += str.substr(j, end_length);
                    if (substrings.find(current_substring) == substrings.end()) {
                        substrings_count++;
                    }
                    substrings.insert(current_substring);
                }
            }
            current_substring = "";
        }
    }
    return substrings_count;
}
int main() {
    string str = "getmesomecoffee";
    string start = "m";
    string end = "e";
    cout << getSubstringsCount(str, start, end) << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が得られます。

6

まとめ

このチュートリアルでは、指定した開始文字列と終了文字列を両方備えた、重複しない部分文字列の個数をC++で求める方法を解説しました。セットを活用した重複除去の考え方は、文字列照合や部分文字列の列挙など、ほかの文字列処理の問題にも幅広く応用できます。ぜひ自分のコードにも取り入れてみてください。本チュートリアルについてご質問がある場合は、コメント欄でお知らせください。