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

ภาพรวม

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

ตัวอย่าง

อินพุต − Str = "tutorialspoint", subStr = "Point"

เอาต์พุต − Given string does not contain substring!

คำอธิบาย − "Point" ไม่ใช่ substring ของ "tutorialspoint" (ตัวพิมพ์เล็ก/ใหญ่ต่างกัน)

อินพุต − Str = "globalization", subStr = "global"

เอาต์พุต − Given string contains substring!

คำอธิบาย − "global" เป็น substring ของ "globalization"

แนวทางการแก้ปัญหา

ตรวจสอบ subStr เป็น substring ของ Str แบบเรียกซ้ำ ขั้นตอน:

• ส่งทั้งสองสตริงให้ฟังก์ชันเรียกซ้ำ พอยน์เตอร์ชี้ตำแหน่งตัวอักษรปัจจุบัน
• หาก Str จบแต่ subStr ยังเหลือ คืน 0 (ไม่พบ)
• หากตัวอักษรปัจจุบันเป็นตัวสุดท้ายของ subStr คืน 1 (พบ)
• หากตัวอักษรทั้งคู่ตรงกัน ขยับพอยน์เตอร์ทั้งคู่ไปตัวถัดไป
• หากไม่ตรง ขยับพอยน์เตอร์ของ Str ไปตัวถัดไป
• ฟังก์ชัน match(char *str1, char *substr1) ตรวจสอบตัวอักษรติดต่อกัน คืน 1 หากตรงทั้งหมด
• ฟังก์ชัน checksubString(char *str2, char *substr2) ค้นหา substr2 ใน str2
• หากตัวอักษรปัจจุบันตรง เรียก match ตรวจสอบต่อเนื่อง หากคืน 1 ให้คืน 1
• หากถึงปลาย str2 คืน 0
• มิฉะนั้น เรียกซ้ำ checksubString(str2+1, substr2)
• พิมพ์ผลตามค่าที่คืนมา

ตัวอย่างโค้ด C++

#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!