C++で文字列の部分文字列の総数を求める方法を解説

この記事では、与えられた文字列から作成できる空でない部分文字列の個数を求める方法について解説します。

入力 : string = "moon"
出力 : 10
説明 : 部分文字列は 'm'、'o'、'o'、'n'、'mo'、'oo'、'on'、'moo'、'oon'、'moon' の 10 個です。

入力 : string = "yellow"
出力 : 21

解法のアプローチ

文字列の長さを n とします。上の例からも分かるように、考えられるすべての部分文字列の個数を求めるには、長さ n、(n-1)、(n-2)、(n-3)、……2、1 の部分文字列の個数を順に加算していく必要があります。

部分文字列の総数 = n + (n - 1) + (n - 2) + (n - 3) + ……. + 2 + 1

= n × (n + 1) / 2

これにより、文字列の長さ n を使って部分文字列の個数を計算する式が導かれました。

C++による実装

以下は、この問題を解くために使用できる C++ のコードです。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int main () {
    string str = "yellow";
    // 文字列の長さを求める
    int n = str.length();
    // 導出した式から結果を計算する
    int number_of_strings = n * (n + 1) / 2;
    cout << "Number of substrings of a string : " << number_of_strings;
    return 0;
}

実行結果

Number of substrings of a string : 21

コードの解説

これは、与えられた文字列から作成可能な部分文字列の個数を求めるための、最も効率的でシンプルなアプローチです。

まずコード内では、length() 関数を使って文字列の長さを取得し、その値を先ほど導出した式に代入します。そして、結果を格納した変数の値を出力として表示します。

まとめ

この記事では、文字列に含まれる部分文字列の個数を求める方法を解説しました。まず、すべての可能な部分文字列の個数を求める式を導出し、文字列の長さをもとにその式から結果を得る流れを紹介しました。同じプログラムは、C、Java、Python など他の言語でも記述することができます。この記事が皆さんのお役に立てば幸いです。