C++에서 부분 문자열 검색을 수행하는 재귀 함수

<시간/>

두 개의 문자열 Str 및 subStr이 입력으로 제공됩니다. 목적은 subStr에 있는 텍스트가 Str에 부분 문자열로 존재하는지 여부를 찾는 것입니다. 전체 X가 Y에 한 번 이상 존재하는 경우 문자열 X를 Y의 하위 문자열이라고 합니다. 이를 수행하기 위해 재귀적 접근 방식을 사용합니다.

예

입력 − Str ="튜토리얼 포인트" subStr="포인트"

출력 − 주어진 문자열에 하위 문자열이 포함되어 있지 않습니다!

설명 − 문자열 Point는 tutorialspoint의 하위 문자열이 아닙니다.

입력 − Str ="세계화" subStr="전역"

출력 − 주어진 문자열에 하위 문자열이 포함되어 있습니다!

설명 − 문자열 global은 세계화의 하위 문자열입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서 우리는 subStr이 재귀적 방식으로 Str의 부분 문자열인지 확인합니다. 재귀 단계는 다음과 같습니다.-

1. 포인터가 두 문자열의 현재 문자 위치를 가리키는 재귀 함수에 두 문자열을 전달합니다.
문자열이 종료되었지만 패턴에 더 많은 문자가 남아 있으면 패턴을 찾을 수 없고 문자열 끝에 도달했기 때문에 0을 반환합니다.
현재 문자가 패턴의 마지막 문자인 경우 문자열에서 찾은 경우 1을 반환합니다.
현재 두 문자가 같으면 두 포인터를 다음 위치로 이동합니다.
현재 두 문자가 모두 일치하지 않으면 string에 대한 포인터를 다음 위치로 이동합니다.
입력 문자열을 문자 배열 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가 가리키는 현재 문자가 같으면 연속된 문자도 일치() 함수를 사용하여 일치하는지 확인합니다. 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!