문자열 패턴 검색: 1 - Naive 패턴 검색 (Naive Pattern Searching)

설명

Naive 패턴 검색 알고리즘은, 문자열에서 패턴을 찾는 가장 단순한 방법이다.

패턴을 텍스트 위로 하나씩 밀어서 일치하는지 확인하고, 일치하는 것이 발견되면, 1개씩 다시 밀어서 다음에 일치하는 항목을 확인한다.

 

코드(C++)

#include <iostream>
#include <string>

using namespace std;

void search(string &pat, string &txt) {
    int M = pat.size();
    int N = txt.size();

    for (int i = 0; i <= N - M; ++i) {
        int j;

        for (j = 0; j < M; ++j) {
            if(txt[i + j] != pat[j])
                break;
        }

        if(j == M) {
            cout << "pattern found at: " << i << "\n";
        }
    }
}

int main() {
    // Example 1
    string txt1 = "AABAACAADAABAABA";
    string pat1 = "AABA";
    cout << "Example 1: " << endl;
    search(pat1, txt1);
    
    // Example 2
    string txt2 = "agd";
    string pat2 = "g";
    cout << "\nExample 2: " << endl;
    search(pat2, txt2);
    return 0;
}

 

 

Example 1: 
pattern found at: 0
pattern found at: 9
pattern found at: 12

Example 2: 
pattern found at: 1

 

 

복잡도 분석

시간 복잡도: O(n * m) - n은 문자열의 길이, m은 패턴의 길이

공간 복잡도: O(1) - 인덱스 변수만을 사용

 

만약에 하나의 패턴만 찾는 경우라면, 시간 복잡도는 최상의 경우 O(m)이 될 수 있다.(시작 지점부터 패턴 발견)

최악에는 O(n*m)이다.(패턴이 없거나, 맨 마지막에 등장)

 

 

출처

https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/?ref=shm