C++에서 벡터(Vector)를 활용한 문자열 패턴 검색 프로그램 구현하기

개요

벡터를 활용한 문자열 매칭은 널리 알려진 문자열 검색 기법 중 하나입니다. 이 방식에서는 메인 문자열 안에서 특정 부분 문자열(패턴)을 벡터(vector)를 이용해 탐색합니다.

C++에서는 표준 라이브러리(STL)를 통해 벡터를 손쉽게 생성할 수 있습니다. 먼저 메인 문자열과 검색 대상 문자열을 각각 벡터로 변환한 뒤, 메인 문자열 내부에서 패턴을 검색합니다. 일치하는 항목을 발견하면 함수는 해당 위치를 반환하고, 동시에 메인 문자열에서 그 부분을 제거합니다. 이렇게 처리하면 다음 반복에서는 항상 시작 위치(0번째)부터 다시 검색을 진행할 수 있습니다.

패턴이 여러 번 등장하는 경우에는 루프를 사용해 매칭 작업을 반복 수행하며, 패턴을 발견할 때마다 해당 위치를 반환합니다.

입력 및 출력 예시

입력: 메인 문자열: "ABAAABCDBBABCDDEBCABC", 패턴 "ABC"
출력: 패턴 발견 위치: 4
      패턴 발견 위치: 10
      패턴 발견 위치: 18

알고리즘

vector_pattern_search(main, substr)

입력 − 메인 텍스트와 검색할 부분 문자열

출력 − 패턴이 발견된 위치

Begin
    p := main 문자열의 시작 지점
    while r이 substr의 끝에 도달하지 않고, p가 main의 끝에 도달하지 않으면:
        r := substr의 시작 지점
        while p와 r 위치의 요소가 서로 다르고, p가 main 범위 내에 있으면:
            p := p + 1
            i := i + 1
        done
        q := p
        while p와 r 위치의 요소가 같고, r이 substr 범위 내이며 p가 main 범위 내에 있으면:
            p := p + 1
            i := i + 1
            r := r + 1
        done
        if r이 substr의 끝을 초과하면:
            main에서 첫 번째로 발견된 substr 삭제
            substr가 발견된 위치 반환

        if p가 main 문자열의 끝을 초과하면:
            return 0
        q := q + 1
        p := q
    done
End

예제 코드

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

void take_string(vector<char> &string){
    char c;
    while(true){
        c = getchar();
        if(c == '\n'){
            break;
        }
        string.push_back(c);
    }
}

void display(vector<char> string){
    for(int i = 0; i<string.size(); i++){
        cout << string[i];
    }
}

int match_string(vector<char>& main, vector<char> substr){
    vector<char>::iterator p,q, r;
    int i = 0;

    p = main.begin();

    while (r <= substr.end() && p <= main.end()){
        r = substr.begin();
        while (*p != *r && p < main.end()){
            p++;
            i++;
        }
        q = p;

        while (*p == *r && r <= substr.end() && p<=main.end()){
            p++;
            i++;
            r++;
        }

        if (r >= substr.end()){
            main.erase(main.begin(), q + 1);
            return (i - substr.size() + 1);
        }

        if (p >= main.end())
            return 0;
            p = ++q;
    }
}

실행 결과

Enter main String: C++ is programming language. It is object oriented language
Enter substring to find: language

Match found at Position = 20
Match found at Position = 52

위 실행 결과에서 볼 수 있듯이, 긴 문장 안에서 "language"라는 단어가 두 번 등장하며, 프로그램은 각각의 위치(20번째, 52번째)를 정확하게 찾아내어 출력합니다. 이처럼 벡터 기반 검색은 패턴이 여러 번 나타나는 경우에도 반복적인 탐색을 통해 모든 위치를 효과적으로 찾아낼 수 있습니다.