【C++】文字列から作成可能な長さnの部分文字列の個数を求める方法

文字列str[]と整数nが与えられたとき、str[]から取り出すことのできる「長さnの部分文字列」が全部でいくつあるかを求めるのがこの問題の狙いです。例えば、文字列が「abcde」でn=3の場合、長さ3の部分文字列は「abc」「bcd」「cde」の3つとなり、個数は3になります。

具体例で理解する

入力: str[] = "computer"、n = 4
出力: 与えられた文字列から作成可能な長さnの部分文字列の個数は 5
解説: 長さ4の部分文字列は「comp」「ompu」「mput」「pute」「uter」の5つです。

入力: str[] = "development"、n = 5
出力: 与えられた文字列から作成可能な長さnの部分文字列の個数は 7
解説: 長さ5の部分文字列は「devel」「evelo」「velop」「elopm」「lopme」「opmen」「pment」の7つです。

プログラムのアプローチ

文字列str[]の長さをLとすると、str[]内に含まれる長さnの部分文字列の個数は「L − n + 1」で求められます。例えば、文字列「abcdefghi」(L=9)でn=4の場合、部分文字列は「abcd」「bcde」「cdef」「defg」「efgh」「fghi」の6つとなり、9 − 4 + 1 = 6で計算結果と一致します。これは、長さnの部分文字列の開始位置が0からL−nまでのL−n+1通りしかないためです。

• 文字列strを受け取ります。

• nを整数として受け取ります。

• 関数possible_substring(string str, int length, int n)は、文字列とその長さ、nを受け取り、長さnの部分文字列の個数を返します。

• 変数countを用意し、count = length − n + 1 を設定します。

• 最後にcountを結果として返します。

なお、nが文字列長より大きい場合には作成できる部分文字列が存在しないため、実用的なコードではcountが負の値にならないようチェックを追加しておくとより安全です。

コード例

#include <bits/stdc++.h>
using namespace std;
int possible_substring(string str, int length, int n){
    int count = length - n + 1;
    return count;
}
int main(){
    string str = "learning";
    int length = str.length();
    int n = 2;
    cout<<"Count of substrings of length n possible from the given string are: "<<possible_substring(str, length, n);
    return 0;
}

出力

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

Count of substrings of length n possible from the given string are: 7