Cho hai chuỗi Str và subStr làm đầu vào. Mục đích là để tìm xem văn bản có trong subStr có tồn tại trong Str dưới dạng chuỗi con hay không. Chuỗi X được gọi là chuỗi con của Y nếu toàn bộ X có trong Y ít nhất một lần. Chúng tôi sẽ sử dụng phương pháp đệ quy để thực hiện điều này.
Ví dụ
Đầu vào - Str =“tutorialspoint” subStr =”Point”
Đầu ra - Chuỗi đã cho không chứa chuỗi con!
Giải thích - Chuỗi Point không phải là chuỗi con của điểm hướng dẫn
Đầu vào - Str =“toàn cầu hóa” subStr =”toàn cầu”
Đầu ra - Chuỗi cho trước chứa chuỗi con!
Giải thích - Chuỗi toàn cầu là chuỗi con của toàn cầu hóa
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi kiểm tra xem subStr có phải là chuỗi con của Str theo cách đệ quy hay không. Các bước cho đệ quy sẽ là:-
-
1. Chuyển cả hai chuỗi vào một hàm đệ quy nơi con trỏ sẽ trỏ đến vị trí ký tự hiện tại của cả hai chuỗi
-
Nếu chuỗi đã kết thúc nhưng mẫu còn lại nhiều ký tự thì trả về 0 vì không tìm thấy mẫu và chúng ta đã đến cuối chuỗi.
-
Nếu ký tự hiện tại là ký tự cuối cùng trong mẫu thì nó được tìm thấy trong chuỗi, trả về 1.
-
Nếu cả hai ký tự hiện tại đều giống nhau, thì hãy di chuyển cả hai con trỏ đến các vị trí tiếp theo.
-
Nếu cả hai ký tự hiện tại không khớp, thì hãy di chuyển con trỏ cho chuỗi sang vị trí tiếp theo.
-
Lấy các chuỗi đầu vào dưới dạng mảng ký tự Str và subStr.
-
Đối sánh hàm (char * str1, char * substr1) nhận hai chuỗi con và trả về 1 nếu substr1 và str1 giống nhau.
-
Cả hai con trỏ đều trỏ đến các ký tự có trong chuỗi, ban đầu ở vị trí bắt đầu.
-
Nếu substr trống, thì trả về 0.
-
Nếu cả hai chuỗi đều trống, thì cũng trả về 0.
-
Nếu cả hai ký tự hiện tại đều bằng nhau thì kiểm tra đệ quy các ký tự tiếp theo bằng cách sử dụng khớp (str1 + 1, substr1 + 1)
-
Hàm checksubString (char * str2, char * substr2) nhận cả hai chuỗi và trả về 1 nếu substr2 có trong str2.
-
Nếu các ký tự hiện tại được trỏ bởi str2 và substr2 giống nhau thì hãy kiểm tra xem các ký tự liên tiếp có khớp với nhau hay không bằng cách sử dụng hàm match (). Nếu nó trả về 1 thì trả về 1.
-
Nếu đến cuối str2 thì trả về 0.
-
Nếu không, kiểm tra đệ quy ký tự tiếp theo của str2 bằng checksubString (str2 + 1, substr2);
-
Nếu tất cả các điều kiện điều kiện không thành công thì cũng kiểm tra đệ quy bằng cách sử dụngchecksubString (str2 + 1, substr2);
-
In kết quả theo giá trị trả về.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Given string contains substring!