C++でXより大きい数値を表す部分文字列の個数を数える方法

0から9までの数字のみで構成される文字列が与えられます。この文字列は1つの10進数を表しているとみなします。ここでの目的は、数値 X よりも大きな値を表す部分文字列がいくつあるかを求めることです。ただし、部分文字列の先頭が「0」で始まってはならないという条件があります。たとえば元の文字列が「2021」の場合、「02」「021」「0」のように先頭が0から始まる部分文字列は候補から除外されます。

この問題は、各開始位置の先頭文字をチェックするだけで効率的に解けます。先頭の文字が「0」以外であれば、そこから始まる部分文字列はすべて有効な候補になります。あとは stoi() を使って部分文字列を整数に変換し、その値が X より大きいかどうかを判定してカウントを増やしていきます。

それでは、具体的な例で確認してみましょう。

入出力例

入力: str = "123"、X = 12
出力: Xより大きい数値を表す部分文字列の個数： 2
説明: 12より大きい部分文字列は「123」と「23」の2つです。

入力: str = "111"、X = 100
出力: Xより大きい数値を表す部分文字列の個数： 1
説明: 100より大きいのは「111」だけです。

プログラムで使用するアプローチ

• 数字のみで構成された文字列 str を受け取ります。
• 文字列の長さを len = str.length() として保存します。
• 関数 greater_X(string str, int x) は、文字列を受け取り、Xより大きい10進数を表す部分文字列の個数を返します。
• forループで文字列を左から右へ走査します。
• インデックス i = 0 から i < len まで順に処理します。
• str[i] が '0' 以外であれば、その位置から始まるすべての部分文字列が有効な候補になります。
• 部分文字列の長さ j を 1 から i + j <= len まで変化させながら試します。
• 部分文字列 str.substr(i, j) を stoi() で整数に変換し、その値が X より大きければ count をインクリメントします。
• 最終的な count を結果として返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int greater_X(string str, int x){
    int count = 0;
    int len = str.length();
    for (int i = 0; i < len; ++i){
        if(str[i] != '0'){
            for (int j=1; (i + j) <= len; ++j){
                if (stoi(str.substr(i, j)) > x){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    string str = "987";
    int x = 100;
    cout<<"Count of number of substrings with numeric value greater than X are: "<<greater_X(str, x);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Count of number of substrings with numeric value greater than X are: 1

計算量と注意点

この手法では、開始位置と部分文字列の長さの組み合わせをすべて調べるため、時間計算量は O(n²) となります（nは文字列の長さ）。また、stoi() は int 型に変換するため、非常に長い部分文字列を変換するとオーバーフローが発生する可能性がある点に注意してください。桁数が多い数値を扱う場合は、stoll() を使うか、文字列の長さ比較を組み合わせて大小関係を判定するなどの工夫が必要になります。