문자열 패턴 매칭 1 - Brute Force

워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다.  이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다.

미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다.

 

문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다.

 - Brute Force

 - Rabin-Karp

 - K.M.P

 - Boyer Moore

이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자.

이번 포스트에서는 각 방법을 사용해보면서 백준의 https://www.acmicpc.net/problem/1786 찾기 문제를 풀어볼 계획이다. 

전체적으로는 검색에 두 가지 문자열을 사용한다.

String target = "ABABABABBABABABAC";    // 전체 문자열
String pattern = "ABABABAC";            // 찾으려는 패턴 문자열

 

 

Brute Force

먼저 살펴볼 방식은 Brute Force 즉 다 해보기다.

설명하기도 민망한 이 알고리즘은 하나씩 모든 문자를 비교해보는 방식이다. 매칭 검색 중 다른 문자가 나오면 패턴을 순회하는 반복을 멈추고 다시 패턴의 처음 부터 비교한다. (문자열 비교 과정에서 일치는 파란색, 불일치는 빨간색으로 표시한다.)

 

검색 과정에서 위의 경우처럼 불일치가 발생하는 경우 타겟의 인덱스를 하나 증가시킨 후 패턴의 처음부터 다시 검색을 시작한다.

 

그러다가 패턴의 전체가 일치하면 타겟의 인덱스인 4를 반환한다.

 

static void bruteForce2(String src, String pattern) {
    for (int i = 0; i < src.length(); i++) {
        boolean match = true;
        for (int j = 0; j < pattern.length(); j++) {
            if (pattern.charAt(j) != src.charAt(i + j)) {
                match = false;
                break;
            }
        }
        if (match) {
            System.out.println(i);
        }
    }
}

 

이 방식은 최악의 시간 복잡도는 문자열의 길이(N) 만큼 패턴의 길이 (M)의 곱이 발생하기 때문에 O(NM)이라고 볼 수 있다.  따라서 성능이 좋은 알고리즘이라고 보기는 힘들다. APS에서 Brute Force를 이용한다면 당연히 시간 초과다.

하지만 실제 우리가 검색할 때는 짧은 단어를 이용해서 검색하기 때문에 M이 매우 짧은 경우가 대부분이다. 이 점을 감안한다면 실생활에서는 그다지 나쁘다고 보기 어렵다.

실제로 c의 strstr()이나 c++의 string:find(), java의 indexOf() 함수등 많은 표준 라이브러리들이 이 방식을 사용한다.

 

Brute Force: https://goodteacher.tistory.com/127
RabinKarp: https://goodteacher.tistory.com/128
KMP: https://goodteacher.tistory.com/129