C++で部分文字列検索を行う再帰関数

入力として2つの文字列StrとsubStrが与えられます。目標は、subStrに存在するテキストがStrにサブストリングとして存在するかどうかを確認することです。文字列Xは、X全体がYに少なくとも1回存在する場合、Yのサブ文字列と呼ばれます。これを行うには、再帰的なアプローチを使用します。

例

入力 − str =“ tutorialspoint” subStr =” Point”

出力 −指定された文字列に部分文字列が含まれていません！

説明 −文字列Pointはtutorialspointのサブ文字列ではありません

入力 − str =“ globalization” subStr =” global”

出力 −指定された文字列に部分文字列が含まれています！

説明 −文字列globalはグローバリゼーションのサブ文字列です

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、subStrが再帰的にStrのサブストリングであるかどうかを確認します。再帰の手順は次のとおりです。-

• 1.両方の文字列を再帰関数に渡します。再帰関数では、ポインタが両方の文字列の現在の文字位置を指します

• 文字列が終了しているが、パターンにさらに文字が残っている場合は、パターンが見つからず、文字列の最後に到達したため、0を返します。

• 現在の文字がパターンの最後の文字である場合、それは文字列で見つかります。1を返します。

• 現在の両方の文字が同じである場合は、両方のポインターを次の位置に移動します。

• 現在の両方の文字が一致しない場合は、文字列のポインタを次の位置に移動します。

• 入力文字列を文字配列StrおよびsubStrとして取得します。

• 関数match（char * str1、char * substr1）は、2つのサブ文字列を受け取り、substr1とstr1が同じ場合は1を返します。

• 両方のポインタは、最初は開始位置にある文字列に存在する文字を指します。

• substrが空の場合は、0を返します。

• 両方の文字列が空の場合は、0も返します。

• 現在の両方の文字が等しい場合は、match（str1 + 1、substr1 + 1）を使用して次の文字を再帰的にチェックします

• 関数checksubString（char * str2、char * substr2）は両方の文字列を受け取り、substr2がstr2に存在する場合は1を返します。

• str2とsubstr2が指す現在の文字が同じである場合は、match（）関数を使用して連続する文字も一致するかどうかを確認します。 1を返す場合は、1を返します。

• str2の終わりに達した場合は、0を返します。

• それ以外の場合は、checksubString（str2 + 1、substr2）;

  を使用して、str2の次の文字を再帰的にチェックします。

• すべての条件条件が失敗した場合は、checksubString（str2 + 1、substr2）;

  を使用して再帰的にチェックします。

• 戻り値に従って結果を出力します。

例

#include<iostream>
using namespace std;
int match(char *str1, char *substr1){
   if (*substr1 == '\0'){
      return 1;
   }
   if (*str1 == '\0'){
      if(*substr1 != '\0'){
         return 0;
      }
   }
   if (*str1 == *substr1){
      return match(str1 + 1, substr1 + 1);
   }
   return 0;
}
int checksubString(char *str2, char *substr2){
   if (*str2 == *substr2){
      if(match(str2, substr2)){
         return 1;
      }
   }
   if (*str2 == '\0'){
      return 0;
   }
   else{
      return checksubString(str2 + 1, substr2);
   }

   return checksubString(str2 + 1, substr2);
}
int main(){
   char Str[]="tutorialspoint";
   char subStr[]="point";

   if(checksubString(Str,subStr)==1){
      cout << "Given string contains substring!";
   }
   else{
      cout << "Given string does not contain substring!"; }
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Given string contains substring!