Javaで文字列のすべての部分文字列（サブセット）を検索する方法

はじめに

この記事では、Javaを使って文字列のすべての部分文字列（サブセット）を取り出す方法を解説します。文字列とは、1つ以上の文字が並び、ダブルクォート（" "）で囲まれたデータ型のことです。そして、その文字列の一部として切り出せるものを「部分文字列」と呼びます。

たとえば、入力として "JVM" という文字列を与えた場合、期待される出力は次のようになります。

The string is defined as: JVM

The subsets of the string are:
J
JV
JVM
V
VM
M

長さ n の文字列から取り出せる部分文字列の総数は、n × (n + 1) / 2 個です。上記の例では文字数が3なので、3 × 4 ÷ 2 = 6個の部分文字列が得られます。

アルゴリズム

処理の手順は以下の通りです。

Step 1 - 処理を開始する
Step 2 - 必要な変数を宣言する
Step 3 - 対象となる文字列の値を定義する
Step 4 - 反復ごとにカウントアップする一時変数を初期化する
Step 5 - 二重ループで文字列の長さ分だけ繰り返す
Step 6 - 指定した範囲の部分文字列を切り出し、一時変数をインクリメントする
Step 7 - ループを使ってすべての部分文字列を表示する
Step 8 - 処理を終了する

例1：mainメソッド内にすべての処理を記述する場合

ここでは、すべての操作を main メソッドの中にまとめて記述します。

public class Demo {
   public static void main(String[] args) {
      String input_string = "JVM";
      int string_length = input_string.length();
      int temp = 0;
      System.out.println("The string is defined as: " +input_string);
      String string_array[] = new String[string_length*(string_length+1)/2];
      for(int i = 0; i < string_length; i++) {
         for(int j = i; j < string_length; j++) {
            string_array[temp] = input_string.substring(i, j+1);
            temp++;
         }
      }
      System.out.println("The subsets of the string are: ");
      for(int i = 0; i < string_array.length; i++) {
         System.out.println(string_array[i]);
      }
   }
}

実行結果

The string is defined as: JVM
The subsets of the string are:
J
JV
JVM
V
VM
M

例2：オブジェクト指向スタイルで関数に分割する場合

次に、処理を独立したメソッドにカプセル化し、オブジェクト指向プログラミングらしい構成に書き換えた例を紹介します。

public class Demo {
   static void subsets(String input_string){
      int string_length = input_string.length();
      int temp = 0;
      String string_array[] = new String[string_length*(string_length+1)/2];
      for(int i = 0; i < string_length; i++) {
         for(int j = i; j < string_length; j++) {
            string_array[temp] = input_string.substring(i, j+1);
            temp++;
         }
      }
      System.out.println("The subsets of the string are: ");
      for(int i = 0; i < string_array.length; i++) {
         System.out.println(string_array[i]);
      }
   }
   public static void main(String[] args) {
      String input_string = "JVM";
      System.out.println("The string is defined as: " +input_string);
      subsets(input_string);
   }
}

実行結果

The string is defined as: JVM
The subsets of the string are:
J
JV
JVM
V
VM
M

コードのポイント

• substring(i, j + 1)：開始位置 i から終了位置 j までの範囲を切り出します。終了位置は含まれないため、j + 1 を指定しています。
• 配列サイズ n × (n + 1) / 2：生成される部分文字列の総数と一致させており、無駄のないメモリ確保が可能です。
• 外側のループ（i）：部分文字列の開始位置を制御します。
• 内側のループ（j）：部分文字列の終了位置を制御します。

計算量は二重ループにより O(n²) となります。文字列が長くなっても効率よく動作する、シンプルで実用的なアプローチです。