C++で文字列のすべての部分文字列を出力するプログラムの解説

はじめに

この記事では、与えられた文字列からすべての部分文字列を取り出して出力するC++プログラムについて解説します。

文字列（char型配列）が1つ与えられ、その文字列から生成できるすべての部分文字列を順番に画面へ表示するのが本プログラムの目的です。

部分文字列とは

部分文字列とは、元の文字列から連続する文字を取り出して作られる文字列のことです。例えば「abca」という文字列の場合、「a」「b」「ab」「bca」「abca」などがすべて部分文字列に該当します。

長さnの文字列からは、長さ1の部分文字列がn個、長さ2のものがn-1個、長さ3のものがn-2個…と続くため、部分文字列の総数は n×(n+1)/2 個になります。

アルゴリズムの考え方

すべての部分文字列を出力するには、三重のループを利用します。役割はそれぞれ次のとおりです。

• 外側のループ： 部分文字列の長さ（1からnまで）を決める
• 中間のループ： 部分文字列の開始位置を決める
• 内側のループ： 開始位置から指定した長さ分の文字を1文字ずつ出力する

この構造により、長さの短い部分文字列から順に、取りこぼしなくすべてを出力できます。

サンプルプログラム

#include<bits/stdc++.h>
using namespace std;
//すべての部分文字列を出力する関数
void print_substr(char str[], int n){
    for (int len = 1; len <= n; len++){
        for (int i = 0; i <= n - len; i++){
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
                cout << str[k];
            cout << endl;
        }
    }
}
int main(){
    char str[] = "abca";
    print_substr(str, strlen(str));
    return 0;
}

実行結果

文字列「abca」を入力として実行すると、次の10個の部分文字列が順に出力されます。

a
b
c
a
ab
bc
ca
abc
bca
abca

計算量について

この方法では、部分文字列の総数が n×(n+1)/2 個あり、さらに1つの出力ごとに最大n文字の処理が必要です。そのため、全体の時間計算量は O(n³) となります。

短い文字列であれば問題ありませんが、文字列が長くなるほど処理時間が急激に増加する点には注意が必要です。競技プログラミングなどで大きな入力を扱う場合は、別のアルゴリズムやデータ構造の検討も検討するとよいでしょう。

まとめ

本記事では、C++の三重ループを使って、与えられた文字列のすべての部分文字列を網羅的に出力する方法を紹介しました。シンプルで理解しやすい実装であり、部分文字列の概念やループ処理の基礎を学ぶのに最適な題材です。ぜひ実際にコードを動かして、動作を確認してみてください。