C++ 中用于子字符串搜索的递归函数


给定两个字符串 Str 和 subStr 作为输入。目标是查找 subStr 中存在的文本是否在 Str 中作为子字符串存在。如果整个字符串 X 至少在字符串 Y 中出现一次,则称字符串 X 为字符串 Y 的子字符串。我们将使用递归方法来实现这一点。

例如

输入 − Str = “tutorialspoint” subStr=”Point”

输出 − 给定字符串不包含子字符串!

说明 − 字符串 Point 不是 tutorialspoint 的子字符串

输入 − Str = “globalization” subStr=”global”

输出 − 给定字符串包含子字符串!

说明 − 字符串 global 是 globalization 的子字符串

下面程序中使用的方法如下

在这种方法中,我们以递归的方式检查 subStr 是否是 Str 的子字符串。递归步骤如下:

  • 1. 将两个字符串传递给一个递归函数,其中指针将指向两个字符串的当前字符位置

  • 如果字符串已结束但模式还有更多字符剩余,则返回 0,因为模式未找到并且我们已到达字符串的末尾。

  • 如果当前字符是模式中的最后一个字符,则表示它在字符串中找到,返回 1。

  • 如果两个当前字符相同,则将两个指针都移动到下一个位置。

  • 如果两个当前字符不匹配,则将字符串的指针移动到下一个位置。

  • 将输入字符串作为字符数组 Str 和 subStr。

  • 函数 match(char *str1, char *substr1) 接收两个子字符串,如果 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!

更新于: 2021-11-02

1K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告