C++에서 주어진 문자열의 모든 부분 문자열을 출력하는 프로그램

이 튜토리얼에서는 C++을 사용하여 주어진 문자열의 모든 부분 문자열(substring)을 출력하는 프로그램을 살펴보겠습니다.

여기서는 하나의 문자열 또는 문자 배열이 입력으로 주어지며, 우리의 목표는 해당 문자열에서 만들 수 있는 모든 부분 문자열을 순서대로 출력하는 것입니다.

접근 방법

모든 부분 문자열을 구하기 위해 세 개의 중첩 반복문을 사용합니다.

• 바깥쪽 루프(len): 출력할 부분 문자열의 길이를 1부터 n까지 결정합니다.
• 중간 루프(i): 각 길이에 대해 부분 문자열의 시작 인덱스를 지정합니다.
• 안쪽 루프(k): 시작 인덱스 i부터 끝 인덱스 j까지의 문자를 하나씩 출력합니다.

길이가 n인 문자열의 부분 문자열 개수는 총 n×(n+1)/2개이므로, 이 방법의 시간 복잡도는 O(n³)이며 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;

// 모든 부분 문자열을 출력하는 함수
void print_substr(char str[], int n){
    for (int len = 1; len <= n; len++){
        for (int i = 0; i <= n - len; i++){
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
                cout << str[k];
            cout << endl;
        }
    }
}

int main(){
    char str[] = "abca";
    print_substr(str, strlen(str));
    return 0;
}

실행 결과

입력 문자열이 "abca"일 때 위 프로그램은 길이가 짧은 순서대로 다음과 같이 모든 부분 문자열을 출력합니다.

a
b
c
a
ab
bc
ca
abc
bca
abca

정리

이 프로그램은 중첩 반복문만으로 간단하게 구현할 수 있으며, 문자열 처리 알고리즘의 기본기를 익히기에 좋은 예제입니다. 참고로 동일한 위치에 같은 문자가 반복되는 경우("abca"의 첫 번째 'a'와 마지막 'a'처럼)에도 서로 다른 위치의 부분 문자열은 모두 별도로 출력된다는 점을 기억하시기 바랍니다.