C++로 문자열의 부분 문자열 개수 구하기: 공식과 구현 방법

이 글에서는 주어진 문자열에서 만들 수 있는 부분 문자열(substring)의 개수(빈 문자열은 제외)를 구하는 다양한 접근 방법을 알아봅니다.

문제 이해하기

먼저 예제를 통해 문제를 살펴보겠습니다.

입력 : string = "moon"
출력 : 10
설명 : 부분 문자열은 'm', 'o', 'o', 'n', 'mo', 'oo', 'on', 'moo', 'oon', 'moon'으로 총 10개입니다.

입력 : string = "yellow"
출력 : 21

풀이 접근 방법

문자열의 길이를 n이라고 가정해 봅시다. 위 예제에서 확인할 수 있듯이, 가능한 모든 부분 문자열의 개수를 구하려면 길이가 n, (n-1), (n-2), (n-3), ..., 2, 1인 부분 문자열의 개수를 각각 더해야 합니다.

총 부분 문자열 개수 = n + (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1

= n × (n + 1) / 2

즉, 등차수열의 합 공식을 활용하면 문자열의 길이 n만 알면 곧바로 전체 부분 문자열의 개수를 계산할 수 있습니다. 이는 반복문으로 일일이 세는 것보다 훨씬 효율적이며, 시간 복잡도도 O(1)로 매우 빠릅니다.

C++ 구현 코드

위 접근 방식을 C++로 구현한 코드는 다음과 같습니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int main () {
    string str = "yellow";
    // 문자열의 길이 구하기
    int n = str.length ();
    // 공식을 이용해 결과 계산
    int number_of_strings = n * (n + 1) / 2;
    cout << "Number of substrings of a string : " << number_of_strings;
    return 0;
}

실행 결과

Number of substrings of a string: 21

코드 설명

이 방법은 주어진 문자열에서 가능한 부분 문자열의 개수를 구하는 가장 간결하고 효율적인 접근 방식입니다.

코드의 동작 순서는 다음과 같습니다.

1. .length() 함수를 사용하여 입력 문자열의 길이를 구합니다.
2. 앞서 유도한 공식 n × (n + 1) / 2에 길이 값을 대입하여 결과를 계산합니다.
3. 계산된 결과를 화면에 출력합니다.

예를 들어 "yellow"의 길이는 6이므로, 6 × 7 / 2 = 21개의 부분 문자열이 존재하게 됩니다.

마무리

이번 글에서는 문자열에 포함된 부분 문자열의 총 개수를 구하는 방법을 살펴보았습니다. 핵심은 모든 경우를 직접 세기 전에 등차수열의 합 공식을 먼저 유도하고, 문자열의 길이만으로 결과를 즉시 얻어내는 것입니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있으니, 여러 언어로 직접 구현해 보면서 개념을 확실히 익혀보시기 바랍니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.