Javaで部分文字列の出現回数を再帰的にカウントする方法

2つの文字列 str1 と str2 が与えられたとき、再帰的な処理を用いて、文字列 str1 の中に部分文字列 str2 が出現する回数を数えることが目標です。

ここでいう再帰関数とは、定義の中で自分自身を呼び出す関数のことを指します。

たとえば、str1 が「I know that you know that i know」、str2 が「know」である場合、出現回数は 3 となります。

具体例で理解しよう

入力例1

str1 = "TPisTPareTPamTP", str2 = "TP";

出力例1

Count of occurrences of a substring recursively are: 4

説明

部分文字列「TP」は str1 の中に4回出現します。

入力例2

str1 = "HiHOwAReyouHiHi", str2 = "Hi";

出力例2

Count of occurrences of a substring recursively are: 3

説明

部分文字列「Hi」は str1 の中に3回出現します。

プログラムのアプローチ

このアプローチでは、Java の contains() メソッドを使って、str1 の中に str2 が存在するかどうかを調べます。存在する場合は true が返されます。true だった場合には、replaceFirst() メソッドを使って最初の出現箇所を空文字列（""）に置き換えて取り除き、戻り値に 1 を加えることでカウントを増やしていきます。

具体的な手順は以下の通りです。

• 2つの文字列 str1 と str2 を用意します。
• 再帰メソッド subsrting_rec(String str, String sub) は、文字列 str とその部分文字列 sub を受け取り、sub が str 内に出現する回数を返します。
• str.contains(sub) が true かどうかを確認します（str が sub を含んでいるか）。
• true の場合は、str.replaceFirst(sub, "") を使って最初の出現箇所を空文字列に置き換えます。
• この処理を subsrting_rec(String str, String sub) への再帰呼び出しの中で繰り返します。
• すべての再帰呼び出しが終わった時点で、各戻り値の合計が出現回数となります。
• 最後に結果を出力します。

実装例

public class recursive{
    public static void main(String args[]){
        String str1 = "TPisTPareTPamTP", str2 = "TP";
        System.out.println("Count of occurrences of a substring recursively are: "+subsrting_rec(str1, str2));
    }
    static int subsrting_rec(String str, String sub){
        if (str.contains(sub)){
            return 1 + subsrting_rec(str.replaceFirst(sub, ""), sub);
        }
        return 0;
    }
}

実行結果

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

Count of occurrences of a substring recursively are: 4

このように、contains() で部分文字列の存在を確認し、replaceFirst() で見つかった箇所を削除しながら自分自身を再帰的に呼び出すことで、シンプルなコードで出現回数を数えることができます。ただし、非常に長い文字列を扱う場合には再帰の深さに注意が必要です。そのようなケースでは、ループ処理や indexOf() を活用した反復的な実装を検討するとよいでしょう。