문제 개요
문자열 str과 또 다른 부분 문자열 sub_str이 주어졌을 때, str 안에서 sub_str이 등장하는 모든 위치의 인덱스를 찾아야 합니다. 예를 들어 str이 "aabbababaabbbabbaaabba"이고 sub_str이 "abb"라고 가정해 보겠습니다. 이 경우 "abb"가 나타나는 인덱스는 1, 9, 13, 18입니다.
substr() 함수를 이용한 해결 방법
이 문제는 C++ STL에서 제공하는 substr() 함수를 사용하면 손쉽게 해결할 수 있습니다. substr() 함수는 다음 두 가지 인자를 받습니다.
- 시작 위치 — 검사를 시작할 인덱스
- 길이 — 추출할 부분 문자열의 길이
즉, 원본 문자열의 처음부터 끝까지 한 글자씩 이동하면서 substr()으로 추출한 문자열이 sub_str과 일치하는지 비교하고, 일치할 때마다 해당 시작 인덱스를 출력하면 됩니다.
구현 예제 코드
#include<iostream>
using namespace std;
void substrPosition(string str, string sub_str) {
bool flag = false;
for (int i = 0; i < str.length(); i++) {
if (str.substr(i, sub_str.length()) == sub_str) {
cout << i << " ";
flag = true;
}
}
if (flag == false)
cout << "NONE";
}
int main() {
string str = "aabbababaabbbabbaaabba";
string sub_str = "abb";
cout << "Substrings are present at: ";
substrPosition(str, sub_str);
}
실행 결과
Substrings are present at: 1 9 13 18
코드 동작 원리
- 루프 변수
i가 0부터str.length() - 1까지 순회합니다. - 매 반복마다
str.substr(i, sub_str.length())로i번째 위치에서sub_str길이만큼의 부분 문자열을 추출합니다. - 추출된 문자열이
sub_str과 같으면 현재 인덱스i를 출력하고flag를 true로 설정합니다. - 끝까지 일치하는 구간이 없다면
flag가 false로 남아 있으므로 "NONE"을 출력합니다.
이 방법의 시간 복잡도는 O(n × m)입니다. 여기서 n은 str의 길이, m은 sub_str의 길이이며, 입력 크기가 크지 않다면 충분히 실용적인 성능을 보여줍니다.
대안: find() 함수 활용하기
C++의 string::find() 함수를 사용하면 코드를 더욱 간결하게 작성할 수도 있습니다. find()는 두 번째 인자로 탐색을 시작할 위치를 받을 수 있기 때문에, 발견된 지점 바로 다음 칸부터 이어서 검색하면 모든 등장 위치를 구할 수 있습니다.
#include<iostream>
using namespace std;
void findAllOccurrences(string str, string sub_str) {
size_t pos = str.find(sub_str);
while (pos != string::npos) {
cout << pos << " ";
pos = str.find(sub_str, pos + 1);
}
}
int main() {
string str = "aabbababaabbbabbaaabba";
string sub_str = "abb";
cout << "Occurrences at: ";
findAllOccurrences(str, sub_str);
}
이 코드 역시 앞선 예제와 동일하게 1 9 13 18을 출력합니다.
마무리
정리하면, C++에서 문자열 내 부분 문자열의 모든 등장 인덱스를 찾는 대표적인 방법은 두 가지입니다. substr()과 단순 반복문을 조합하는 방법, 그리고 find() 함수를 반복 호출하는 방법입니다. 두 방식 모두 구현이 간단하고 직관적이므로, 문제 상황과 취향에 맞게 선택하여 사용하면 됩니다.