이 글에서는 하나의 원본 문자열 안에서 특정 패턴(부분 문자열)이 몇 번, 어느 위치에 나타나는지 반복적으로 검색하는 C++ 프로그램을 다룹니다. 이러한 문자열 탐색 기법은 텍스트 편집기의 찾기 기능이나 대용량 문서 분석 등 다양한 곳에서 활용됩니다.
알고리즘
가장 기본적인 방법인 브루트 포스(Brute Force) 방식을 사용합니다. 원본 문자열의 각 위치에서 시작하여 패턴과 한 글자씩 비교하며 일치 여부를 확인합니다.
시작
원본 문자열(org)과 검색할 패턴(patt)을 입력받는다.
org_len = 원본 문자열의 길이 저장
pat_len = 패턴의 길이 저장
i = 0부터 (org_len - pat_len)까지 반복
j = 0부터 pat_len - 1까지 반복
org[i + j] != patt[j]이면 내부 반복 종료
j == pat_len이면 일치 횟수 m 증가 및 위치 출력
m == 0이면 "일치 없음" 출력
아니면 총 발견 횟수 출력
종료알고리즘 핵심 포인트
외부 반복문은 비교를 시작할 수 있는 마지막 위치인 org_len - pat_len까지만 진행합니다. 그 이후 위치에서는 남은 문자 수가 패턴 길이보다 짧아 일치가 불가능하기 때문입니다.
C++ 코드 예제
#include<iostream>
#include<string.h>
using namespace std;
int main() {
char org[150], patt[150];
int i, j, m = 0, org_len, pat_len;
cout << "\n원본 문자열 입력:";
cin >> org;
cout << "검색할 패턴 입력:";
cin >> patt;
org_len = strlen(org); // 원본 문자열의 길이 저장
pat_len = strlen(patt); // 패턴의 길이 저장
for (i = 0; i <= (org_len - pat_len); i++) {
for (j = 0; j < pat_len; j++) {
if (org[i + j] != patt[j])
break;
}
if (j == pat_len) {
m++;
cout << "\n패턴 발견 위치: " << i;
}
}
if (m == 0)
cout << "\n일치하는 결과가 없습니다.";
else
cout << "\n총 발견 횟수 = " << m;
return 0;
}코드 설명
1. 입력 단계: cin으로 원본 문자열과 검색할 패턴을 입력받습니다. 공백 없이 연속된 문자열만 입력 가능하다는 점에 유의하세요.
2. 길이 계산: strlen() 함수를 사용해 두 문자열의 길이를 각각 저장합니다.
3. 이중 반복문 탐색: 외부 반복문은 원본 문자열의 시작 위치를 이동시키고, 내부 반복문은 해당 위치부터 패턴 길이만큼 한 글자씩 비교합니다. 중간에 불일치가 발생하면 break로 빠져나와 다음 위치로 넘어갑니다.
4. 일치 판정: 내부 반복문이 끝까지 완료되면 j == pat_len 조건이 참이 되어 일치로 판정하고, 카운터 m을 증가시키며 위치를 출력합니다.
실행 결과
원본 문자열 입력:thisistutorialspoint.thisisac++program 검색할 패턴 입력:is 패턴 발견 위치: 2 패턴 발견 위치: 4 패턴 발견 위치: 23 패턴 발견 위치: 25 총 발견 횟수 = 4
마무리 및 개선 방향
이 프로그램은 시간 복잡도가 최악의 경우 O(n×m)으로, 아주 긴 텍스트에는 비효율적일 수 있습니다. 실무에서 더 큰 데이터를 다룰 때는 KMP(Knuth-Morris-Pratt) 알고리즘이나 보이어-무어(Boyer-Moore) 알고리즘처럼 전처리를 활용해 탐색 속도를 크게 개선한 기법을 사용하는 것이 좋습니다. 또한 std::string과 find() 메서드를 활용하면 더 안전하고 간결하게 구현할 수 있습니다.