C++で再帰関数を使って部分文字列を検索・判定する方法

2つの文字列 Str と subStr が入力として与えられます。この問題の目的は、subStr に含まれるテキストが Str の中に部分文字列として存在するかどうかを判定することです。文字列 X が文字列 Y の中に全体として少なくとも1回出現するとき、X は Y の部分文字列と呼ばれます。

本記事では、再帰的なアプローチを用いてこの問題を解く方法を解説します。

実行例

入力 − Str = 「tutorialspoint」、subStr = 「Point」

出力 − 与えられた文字列に部分文字列は含まれていません!

説明 − 文字列「Point」は「tutorialspoint」の部分文字列ではありません。先頭が大文字のため、大文字と小文字を区別する比較では一致しないからです。

入力 − Str = 「globalization」、subStr = 「global」

出力 − 与えられた文字列に部分文字列が含まれています!

説明 − 文字列「global」は「globalization」の先頭部分にそのまま含まれています。

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

このアプローチでは、subStr が Str の部分文字列であるかどうかを再帰的に判定します。再帰の基本的な流れは次のとおりです。

• 両方の文字列を再帰関数に渡し、ポインタでそれぞれの現在の文字位置を指します。
• 検索対象の文字列が終端に達したのにパターン側にまだ文字が残っている場合は、パターンが見つからなかったとして 0 を返します。
• パターンの最後の文字まで一致した場合は、パターンが見つかったとして 1 を返します。
• 現在の文字同士が一致する場合は、両方のポインタを次の位置へ進めます。
• 現在の文字同士が一致しない場合は、検索対象の文字列側のポインタだけを次の位置へ進めます。

match 関数の処理内容

• 入力文字列は文字配列 Str と subStr として受け取ります。
• 関数 match(char *str1, char *substr1) は2つの文字列を受け取り、substr1 が str1 の先頭から完全に一致する場合に 1 を返します。
• 両方のポインタは、初期状態ではそれぞれの文字列の先頭を指します。
• substr1 が空(終端に達した)場合は、パターンをすべて消費したことになるため 1 を返します。
• str1 が終端に達しているのに substr1 にまだ文字が残っている場合は 0 を返します。
• 両方の現在の文字が等しい場合は、match(str1 + 1, substr1 + 1) として次の文字を再帰的にチェックします。

checksubString 関数の処理内容

• 関数 checksubString(char *str2, char *substr2) は両方の文字列を受け取り、substr2 が str2 に存在する場合に 1 を返します。
• str2 と substr2 の現在の文字が同じ場合は、match() 関数を呼び出して、その後の文字も連続して一致するかを確認します。戻り値が 1 であれば 1 を返します。
• str2 の終端に達した場合は 0 を返します。
• それ以外の場合は、checksubString(str2 + 1, substr2) として str2 の次の文字から再帰的にチェックを続けます。
• 最終的な戻り値に応じて結果を出力します。

サンプルコード

#include <iostream>
using namespace std;

// str1 の先頭から substr1 が一致するかを再帰的に判定する
int match(char *str1, char *substr1){
    if (*substr1 == '\0'){
        return 1;   // パターンをすべて消費した = 一致
    }
    if (*str1 == '\0'){
        return 0;   // 文字列が先に終端に達した = 不一致
    }
    if (*str1 == *substr1){
        return match(str1 + 1, substr1 + 1);
    }
    return 0;
}

// substr2 が str2 の部分文字列かどうかを再帰的に判定する
int checksubString(char *str2, char *substr2){
    if (*str2 == *substr2){
        if(match(str2, substr2)){
            return 1;
        }
    }
    if (*str2 == '\0'){
        return 0;
    }
    return checksubString(str2 + 1, substr2);
}

int main(){
    char Str[] = "tutorialspoint";
    char subStr[] = "point";

    if(checksubString(Str, subStr) == 1){
        cout << "与えられた文字列に部分文字列が含まれています!";
    }
    else{
        cout << "与えられた文字列に部分文字列は含まれていません!";
    }
    return 0;
}

出力

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

与えられた文字列に部分文字列が含まれています!

この例では、「tutorialspoint」の末尾に「point」が含まれているため、一致が検出されています。なお、subStr を「Point」(先頭が大文字)に変更すると、比較で大文字・小文字が区別されるため一致せず、「部分文字列は含まれていません」という結果になります。