짧은 텍스트를 위한 문자열 검색 알고리즘 구현 C++ 프로그램

이 C++ 프로그램에서는 텍스트(원본 문자열)와 패턴(검색할 문자열)을 입력으로 받습니다. 그다음 텍스트 안에서 패턴을 검색하여 패턴이 나타나는 모든 위치와 총 개수를 출력으로 보여줍니다.

알고리즘

Begin
    문자열과 패턴을 입력으로 받습니다.
    원본 배열과 복사 배열을 각각 선언합니다.
    원본 문자열과 복사 문자열의 길이를 len_ori와 len_dupli에 저장합니다.
    검색하려는 패턴의 위치를 찾기 위한 반복문을 수행합니다.
    패턴이 발견되지 않으면 "찾지 못함"을 출력하고, 발견되면 검색된 패턴의 개수를 출력합니다.
End

동작 방식

이 알고리즘은 가장 기본적인 완전 탐색(Brute Force) 방식으로 동작합니다. 텍스트의 첫 번째 위치부터 시작하여 패턴 길이만큼의 문자들을 하나씩 비교하고, 중간에 일치하지 않는 문자가 나오면 바로 다음 위치로 이동합니다. 내부 반복문이 패턴의 끝까지 도달했다는 것(j == len_dupli)은 해당 위치에서 패턴 전체가 일치했음을 의미하며, 이때 개수를 세고 위치를 출력합니다.

예제 코드

#include<iostream>
#include<cstring>
using namespace std;

int main() {
    char ori[120], dupli[120];
    int i, j, k = 0, len_ori, len_dupli;

    cout<<"enter string without any blank space"<<endl;

    cout<<"\nEnter Original String:";
    cin>>ori;

    cout<<"Enter Pattern to Search:";
    cin>>dupli;

    len_ori = strlen(ori);
    len_dupli = strlen(dupli);

    for (i = 0; i <= (len_ori - len_dupli); i++) { // 패턴의 위치를 찾기 위한 반복문
        for (j = 0; j < len_dupli; j++) {
            if (ori[i + j] != dupli[j])
                break;
        }
        if (j == len_dupli) {
            k++;
            cout<<"\nPattern Found at Position: "<<i;
        }
    }
    if (k == 0)
        cout<<"\nNo Match Found!";
    else
        cout<<"\nTotal Instances Found = "<<k;
    return 0;
}

실행 결과

enter string without any blank space

Enter Original String: Enter Pattern to Search:
Pattern Found at Position: 0
Pattern Found at Position: 1
Pattern Found at Position: 2
Pattern Found at Position: 3
Total Instances Found = 4

위 실행 결과처럼 겹쳐 나타나는 경우도 모두 포함됩니다. 예를 들어 원본 문자열이 "aaaaa"이고 검색 패턴이 "aa"라면, 인덱스 0, 1, 2, 3의 네 곳에서 패턴이 발견됩니다.

참고 사항

cin >>로 입력받기 때문에 문자열에 공백을 포함할 수 없으며, 공백 없이 입력해야 합니다. 또한 이 방식의 시간 복잡도는 O(n×m)으로 짧은 텍스트에는 적합하지만, 긴 텍스트를 다룰 때는 KMP(Knuth–Morris–Pratt)나 Boyer–Moore 같은 더 효율적인 알고리즘을 사용하는 것이 좋습니다.