문자열 알고리즘 (1) - 부르트 포스 (Brute Force, Naive Search)

1. 문자열 패턴 매칭이란?

• 문자열 패턴매칭은 어떤 전체 글에서 원하는 문자열의 위치나 유무를 찾는 것
• 구글크롬에서 컨트롤 + F를 누르고 문자열을 검색하면 문자열 패턴매칭이 이루어짐. 

 

[그림] 문자열 패턴매칭

 

2. Naive Search

• 나이브서치는 단순한 문자열 탐색 방법, loop를 이용해 1~3, 2~4, 3~5, ... m-n~m까지 서치.
• 시간복잡도 : O(nm), 속도는 매우 느리지만 구현이 간편하다.

 

[그림] 나이브 서치

 

3. Brute Force (부르트 포스) 기법

이렇게 무식하게 다 찾아서 해보는 방법을 부르트포스 (무차별 공격) 기법이라고 한다. 예를 들어 0~9까지 4자리의 비밀번호가 걸려있는 자물쇠가 있다고 해보자. 이 경우 비밀번호를 찾아내려면 그냥 loop를 돌면서 1씩 올려보면 언젠가는 찾는다. 이러한 방법론을 통틀어서 부르트포스라고 하고, 나이브서치는 부르트포스 기법중 하나라고 할 수 있다.

 

4. 소스코드

package string;

import java.util.LinkedList;
import java.util.List;

public class NaiveSearch implements StringSearching {

    public static void main(String[] args) {
        StringSearching searching = new NaiveSearch();
        List<Integer> pos = searching.search("hello nice to meet you", "nice");
        System.out.println(pos);
    }


    public List<Integer> search(String whole, String part) {
        List<Integer> results = new LinkedList<>();
        int wholeSize = whole.length(), partSize = part.length();

        for (int i = 0; i <= wholeSize - partSize; i++) {
            boolean find = true;

            for (int j = 0; j < part.length(); j++) {
                if (whole.charAt(i + j) != part.charAt(j)) {
                    find = false;
                    break;
                }
            }

            if (find) {
                results.add(i);
            }
        }

        return results;
    }
}

 

5. Reference