C++로 한 문자열의 부분 문자열이 다른 문자열에 몇 개 존재하는지 찾는 방법

이 글에서는 두 개의 문자열이 주어졌을 때, 첫 번째 문자열의 부분 문자열 중 몇 개가 두 번째 문자열 안에서 발견되는지 그 개수를 구하는 방법을 알아봅니다. 동일한 부분 문자열은 여러 번 등장할 수 있다는 점에 유의하세요.

예시

입력 : string1 = "fogl"
       string2 = "google"
출력 : 6
설명 : string2에 존재하는 string1의 부분 문자열은 [ "o", "g", "l", "og", "gl", "ogl" ] 입니다.

입력 : string1 = "ajva"
       string2 = "java"
출력 : 5
설명 : string2에 존재하는 string1의 부분 문자열은 [ "a", "j", "v", "a", "va" ] 입니다.

문제 해결 접근 방법

예시를 살펴보면 문제의 핵심을 파악할 수 있습니다. 먼저 첫 번째 문자열(string1)에서 만들 수 있는 모든 부분 문자열을 생성하고, 각 부분 문자열이 두 번째 문자열(string2) 안에 존재하는지 하나씩 확인합니다. 존재한다면 카운터 값을 1씩 증가시키고, 전체 문자열에 대한 검사가 끝나면 카운터에 저장된 최종 결과를 출력하면 됩니다.

즉, 이 알고리즘은 크게 두 단계로 나눌 수 있습니다.

1단계 : 이중 반복문을 사용해 string1의 시작 인덱스와 끝 인덱스를 조정하며 가능한 모든 부분 문자열을 생성합니다.
2단계 : 생성된 각 부분 문자열이 string2에 포함되어 있는지 find() 함수로 검사하고, 포함되어 있으면 카운터를 증가시킵니다.

C++ 구현 코드

위에서 설명한 접근 방식을 C++ 코드로 구현하면 다음과 같습니다.

예제 코드

#include<iostream>
#include<string>
using namespace std;

int main() {
    string str1 = "ajva";
    string str2 = "java";
    int count = 0;// 결과를 저장할 카운터
    int n = str1.length();

    for (int i = 0; i < n; i++) {

        string str3; // str3는 str1의 모든 부분 문자열을 저장하기 위해 초기화됨
        for (int j = i; j < n; j++) {
            str3 += str1[j];

            // 해당 부분 문자열이 다른 문자열에 존재하는지 검사
            if (str2.find(str3) != string::npos)
                count++;
        }
    }
    cout << "다른 문자열에 존재하는 한 문자열의 부분 문자열 개수 : " << count;
    return 0;
}

실행 결과

다른 문자열에 존재하는 한 문자열의 부분 문자열 개수 : 5

코드 상세 설명

먼저 코드에서는 두 문자열에 값을 할당하고 카운터를 0으로 초기화합니다. 이후 전체 문자열을 순회하면서 str1에서 만들 수 있는 모든 부분 문자열을 생성하여 str3에 저장합니다. 그런 다음 str1의 각 부분 문자열이 str2에 존재하는지 find() 함수로 확인하고, 존재한다면 카운터를 1씩 증가시킵니다. 마지막으로 카운터 변수에 저장된 값을 출력하여 결과를 확인합니다.

여기서 사용된 find() 함수는 찾고자 하는 문자열이 존재하면 해당 위치의 인덱스를 반환하고, 존재하지 않으면 string::npos를 반환합니다. 따라서 반환값이 npos가 아니라는 조건으로 부분 문자열의 존재 여부를 판별할 수 있습니다.

마무리

이 글에서는 한 문자열의 부분 문자열이 다른 문자열에 몇 개 존재하는지 구하는 간단한 해결 방법을 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 시간 복잡도는 부분 문자열 생성에 O(n²), 각 부분 문자열 검색에 O(n×m)이 소요되므로 전체적으로 O(n³) 수준이며, 입력 크기가 작은 경우 충분히 실용적인 접근 방식입니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.