C++ 재귀 함수로 부분 문자열 검색하기: 구현 원리와 예제 코드

두 개의 문자열 Str과 subStr이 입력으로 주어집니다. 목표는 subStr에 담긴 텍스트가 Str 안에 부분 문자열(substring)로 존재하는지 확인하는 것입니다. 문자열 X가 문자열 Y 안에 최소 한 번 이상 온전히 포함되어 있다면, X를 Y의 부분 문자열이라고 부릅니다.

이 문제는 재귀(recursion) 기법을 활용하여 해결할 수 있습니다.

예제

입력 − Str = "tutorialspoint", subStr = "Point"

출력 − 주어진 문자열은 해당 부분 문자열을 포함하지 않습니다!

설명 − "Point"는 "tutorialspoint"의 부분 문자열이 아니기 때문입니다(대소문자가 다름).

입력 − Str = "globalization", subStr = "global"

출력 − 주어진 문자열은 해당 부분 문자열을 포함합니다!

설명 − "global"은 "globalization" 안에 그대로 포함되어 있는 부분 문자열입니다.

풀이 접근 방식

이 방식에서는 재귀 호출을 통해 subStr이 Str의 부분 문자열인지 여부를 검사합니다. 재귀의 진행 단계는 다음과 같습니다.

두 문자열을 재귀 함수에 전달하고, 각 문자열의 현재 문자 위치를 포인터가 가리키도록 합니다.
문자열은 이미 끝났는데 패턴에는 아직 남은 문자가 있다면, 패턴을 찾지 못한 것이므로 0을 반환합니다.
현재 문자가 패턴의 마지막 문자이고 문자열에서 발견되었다면 1을 반환합니다.
현재 두 문자가 서로 같다면 두 포인터를 모두 다음 위치로 이동합니다.
현재 두 문자가 일치하지 않는다면 문자열 쪽 포인터만 다음 위치로 이동합니다.

match() 함수의 동작

입력 문자열은 문자 배열 Str과 subStr로 받습니다.
함수 match(char *str1, char *substr1)는 두 문자열을 인자로 받아, substr1이 str1과 일치하면 1을 반환합니다.
두 포인터는 각 문자열의 문자를 가리키며, 초기에는 시작 위치를 가리킵니다.
substr이 빈 문자열이면 0을 반환합니다.
두 문자열이 모두 비어 있는 경우에도 0을 반환합니다.
현재 두 문자가 같다면 match(str1 + 1, substr1 + 1)을 호출하여 다음 문자들을 재귀적으로 검사합니다.

checksubString() 함수의 동작

함수 checksubString(char *str2, char *substr2)는 두 문자열을 인자로 받아, substr2가 str2 안에 존재하면 1을 반환합니다.
str2와 substr2가 가리키는 현재 문자가 같다면, match() 함수를 호출해 이후 연속된 문자들도 일치하는지 확인합니다. 결과가 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!)