C++で文字列内の異なる部分文字列の個数を数える方法

本記事では、与えられた文字列 str に含まれる「異なる部分文字列」の総数を数える方法を解説します。部分文字列とは、既存の文字列から取り出せる文字列のことであり、その長さは元の文字列と同じか、それより短いものになります。

まず、具体例を使って問題とその解き方を確認してみましょう。

入力： str = "wxyz"

出力： 異なる部分文字列の数は 10

説明： 数え上げられる異なる部分文字列は以下の通りです。

wxyz, wxy, wx, w, xyz, xy, x, yz, y, z の10個

入力： str = "zzzz"

出力： 異なる部分文字列の数は 4

説明： 異なる部分文字列は以下の通りです。

zzzz, zzz, zz, z

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

• 文字列 str を入力として受け取ります。

• 空の unordered_set「myset」を宣言します。重複する部分文字列を自動的に除外するために使います。

• i を 0 から開始し、i が文字列のサイズ未満である間、1 ずつ増やしながらループします。

  • ループごとに、新しい空の文字列 space を宣言します。

  • j を i から開始し、j が文字列のサイズ未満である間、1 ずつ増やしながらループします。

  • 各ステップで space に str[j] を連結し、i 文字目から始まる部分文字列を順に作成します。

  • space を myset に挿入します。すでに存在する場合は自動的に無視されます。

• 最後に myset のサイズ（要素数）を出力します。これが異なる部分文字列の総数となります。

コード例

#include<iostream>
#include<unordered_set>
using namespace std;
int main(){
    string str = "aaaa";
    unordered_set<string> myset;
    int i, j;
    for (i = 0; i < str.size(); ++i){
        string space = "";
        for (j = i; j < str.size(); ++j){
            space = space + str[j];
            myset.insert(space);
        }
    }
    cout << "count of distinct substring is: " << myset.size();
    return 0;
}

出力

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

count of distinct substring is: 4

この例では、"aaaa" から取り出せる異なる部分文字列は "a"、"aa"、"aaa"、"aaaa" の4種類だけなので、結果は 4 となります。

計算量について

このアプローチでは、すべての開始位置と終了位置の組み合わせに対して部分文字列を生成するため、時間計算量は O(n²) となり、さらに各挿入時のハッシュ計算も含めると全体で O(n³) になります。空間計算量は、格納される部分文字列の数に応じて最大 O(n²) です。

より大きな文字列を効率的に処理したい場合は、接尾辞配列（Suffix Array）や接尾辞木（Suffix Tree）を利用する手法が有効です。これらを使うと、O(n log n) や O(n) の時間計算量で異なる部分文字列の個数を求めることができます。