ฟังก์ชันแบบเรียกซ้ำเพื่อค้นหาสตริงย่อยใน C ++

กำหนดสองสตริง Str และ subStr เป็นอินพุต เป้าหมายคือการค้นหาว่าข้อความที่มีอยู่ใน subStr มีอยู่ใน Str เป็นสตริงย่อยหรือไม่ สตริง X เรียกว่าสตริงย่อยของ Y หาก X ทั้งหมดมีอยู่ใน Y อย่างน้อยหนึ่งครั้ง เราจะใช้วิธีเรียกซ้ำเพื่อทำสิ่งนี้

ตัวอย่าง

ป้อนข้อมูล − Str =“tutorialspoint” subStr=”Point”

ผลผลิต − สตริงที่ระบุไม่มีสตริงย่อย!

คำอธิบาย − string Point ไม่ใช่ substring ของ tutorialspoint

ป้อนข้อมูล − Str =“โลกาภิวัตน์” subStr=”โลก”

ผลผลิต − สตริงที่ระบุมีสตริงย่อย!

คำอธิบาย − สตริงโกลบอลเป็นสตริงย่อยของโลกาภิวัตน์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะตรวจสอบว่า subStr เป็นสตริงย่อยของ Str ในลักษณะเรียกซ้ำหรือไม่ ขั้นตอนการเรียกซ้ำจะเป็น:-

• 1. ส่งผ่านทั้งสองสตริงไปยังฟังก์ชันแบบเรียกซ้ำ โดยที่พอยน์เตอร์จะชี้ไปที่ตำแหน่งอักขระปัจจุบันของทั้งสองสตริง

• หากสตริงสิ้นสุดแต่รูปแบบมีอักขระเหลืออยู่ ให้คืนค่า 0 เนื่องจากไม่พบรูปแบบและเราไปถึงที่ส่วนท้ายของสตริง

• หากอักขระปัจจุบันเป็นอักขระตัวสุดท้ายในรูปแบบ จะพบในสตริง ให้คืนค่า 1

• หากอักขระปัจจุบันทั้งสองตัวเหมือนกัน ให้ย้ายตัวชี้ทั้งสองไปยังตำแหน่งถัดไป

• หากอักขระปัจจุบันทั้งสองไม่ตรงกัน ให้ย้ายตัวชี้สำหรับสตริงไปยังตำแหน่งถัดไป

• รับสตริงอินพุตเป็นอาร์เรย์อักขระ Str และ subStr.

• การจับคู่ฟังก์ชัน (char *str1, char *substr1) รับสองสตริงย่อยและคืนค่า 1 หาก substr1 และ str1 เหมือนกัน

• ตัวชี้ทั้งสองชี้ไปที่อักขระที่อยู่ในสตริง โดยเริ่มต้นที่ตำแหน่งเริ่มต้น

• หาก substr ว่างเปล่า ให้คืนค่า 0

• หากทั้งสองสตริงว่างเปล่า ให้คืนค่า 0 ด้วย

• หากอักขระปัจจุบันทั้งสองเท่ากัน ให้ตรวจสอบอักขระถัดไปซ้ำๆ โดยใช้การจับคู่ (str1 + 1, substr1 + 1)

• ฟังก์ชัน checksubString(char *str2, char *substr2) รับทั้งสตริงและคืนค่า 1 หาก substr2 มีอยู่ใน str2

• หากอักขระปัจจุบันที่ชี้โดย str2 และ substr2 เหมือนกัน ให้ตรวจสอบว่าอักขระที่ต่อเนื่องกันนั้นตรงกันโดยใช้ฟังก์ชันการจับคู่ () หรือไม่ หากคืนค่า 1 ให้คืนค่า 1

• หากถึงจุดสิ้นสุดของ str2 ให้คืนค่า 0

• มิฉะนั้น ให้ตรวจสอบอักขระถัดไปของ str2 ซ้ำๆ โดยใช้ checksubString(str2 + 1, substr2);

• หากเงื่อนไขทั้งหมดล้มเหลว ให้ตรวจสอบซ้ำโดยใช้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!