Cho hai chuỗi Str và subStr. Mục tiêu là kiểm tra subStr có phải chuỗi con của Str hay không bằng đệ quy. Chuỗi X là chuỗi con của Y nếu X xuất hiện trong Y ít nhất một lần.
Ví dụ
Đầu vào - Str = "tutorialspoint", subStr = "Point"
Đầu ra - Chuỗi không chứa chuỗi con!
Giải thích - "Point" không là chuỗi con của "tutorialspoint" (phân biệt chữ hoa/thường).
Đầu vào - Str = "globalization", subStr = "global"
Đầu ra - Chuỗi chứa chuỗi con!
Giải thích - "global" là chuỗi con của "globalization".
Phương pháp sử dụng trong chương trình dưới đây
Kiểm tra subStr có là chuỗi con của Str bằng đệ quy. Các bước:
1. Truyền hai chuỗi cho hàm đệ quy, con trỏ trỏ đến vị trí ký tự hiện tại của cả hai.
Nếu chuỗi chính hết mà chuỗi con còn ký tự → trả về 0 (không tìm thấy).
Nếu ký tự hiện tại là ký tự cuối của chuỗi con → tìm thấy, trả về 1.
Nếu cả hai ký tự hiện tại bằng nhau → tiến cả hai con trỏ.
Nếu khác nhau → chỉ tiến con trỏ chuỗi chính.
Hàm match(char *str1, char *substr1) kiểm tra substr1 khớp với str1 từ vị trí hiện tại.
Hàm checksubString(char *str2, char *substr2) kiểm tra substr2 có trong str2.
In kết quả theo giá trị trả về.
Ví dụ mã
#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 << "Chuỗi chứa chuỗi con!"; } else{ cout << "Chuỗi không chứa chuỗi con!"; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Chuỗi chứa chuỗi con!