Naive Pattern Searching 알고리즘 ( 무식하게 패턴찾기 )

Reference : https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/

Naive algorithm for Pattern Searching - GeeksforGeeks

예를들어 

- Input : "THIS IS A TEST TEXT", pat[ ] = "TEST"

- output : 10

 

- Input : "AABAACAADAABAABA", pat[ ] = "AABA"

- output : 0 or 9 or 12 

 

이런식으로 패턴문자열을 찾는다고 해보자. 

 

방법은 여러가지 있지만, 그 중에서 가장 무식한 방법으로 해보자. 

이중반복문을 돌아가면서, Text 문자열 인덱스별로, 원하는 패턴이 있는지 찾는 방식이다. 

 

* Naive Pattern Searching Algorithm 

- 시간복잡도( Time Complexity ) : O( NM ) ( N : Text length, M : Pattern length )

- 공간복잡도( Auxiliary Space ) : O(1)

 

// C++ program for Naive Pattern

// Searching algorithm

#include <iostream>

#include <string.h>

 

using namespace std;

 

void search(char* pat, char* txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

    /* A loop to slicde pat[ ] one by one */

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

    {

        int j;

       

        // For current index i, check for pattern match

        for(j = 0; j < M; ++j)

        {

            if(txt[i + j] != pat[j])

                break;

        }

        if(j == M) // if pat[0...M-1] = txt[i, i+1, ... i + M - 1]

        {

            cout << "Pattern found at index : " << i << '\n';

        }

    }

}

 

int main()

{

    char txt[] = "AABAACAADAABAABAA";

    char pat[] = "AABA";

    // Function call

    search(pat, txt);

    return 0;

}