Intro

앞서 요번 주에는 보이어-무어 알고리즘을 다룰까 했으나, 학습을 진행하며 KMP 알고리즘이 순서 상 먼저 오는 것이 좋을 것 같아, 이를 먼저 포스팅하고자 한다.

게다가 이번에 가지고 온 백준 예시의 경우, Boyer-Moore 알고리즘을 사용할 경우, 오히려 Fail을 하게 되는 경우여서 특히 유의미한 예시가 되고 전반적인 문자열 검색 알고리즘에 대해 알아 보고자 한다.

문자열 검색 알고리즘

우선 위키백과에 나와 있는 정의를 한 번 알아보자.
문자열 검색 알고리즘(string-searching algorithm, string-matching algorithm)은 문자열을 다루는 알고리즘의 하나로, 특정 문자 또는 문자열을 더 큰 문자열이나 글에서 찾아내는 수법이다.

잘 알려진 종류로 커누스-모리스-프랫(tKnuth-Morris-Prat) 알고리즘이나 아호 코라식(Aho-Corasick) 알고리즘 따위가 있다.

오늘 정리해 볼 알고리즘은 KMP 커누스-모리스-프랫 알고리즘이다.

KMP 알고리즘

이름에서도 느껴지겠지만 3명의 사람이 설계한 알고리즘이다. 또한 위에서 알아본 것처럼 문자열 검색 알고리즘의의 일종으로 전체 문자열에서 특정 문자열을 찾는 알고리즘이다.

시간복잡도를 알아 보면 O(N+M)으로 표현하며 이에 대한 문자 내용은 N(전체 문자열 길이), M(패턴 문자열 길이)이다.
해당 빅오 표기법은 2~3주 정도 후에 북스터디 정리로 알아볼 예정이다 :)

위키백과에서 다루고 있는 정의와 내용에 관해서도 간단히 알아보자.
컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다.

문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi)를 사용한다.

vector<int> KMP_GET(string grope){
    int Begin=0, Length = (int)grope.size();
    vector<int> pi(Length, 0);
    for(int i=1 ; i< Length ; i++){
        while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1];
        if(grope[i] == grope[Begin]) pi[i] = ++Begin;
    }
    return pi;
}

위는 위키백과에서 제공하고 있는 C++ 실패함수 계산 코드다. 위 코드로 나온 pi배열 KMP알고리즘 실행중, 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재로, 위의 코드를 자바로 바꿔보았으며 아래는 그에 관한 코드다.

import java.util.Arrays;

public class KMP {
    public static int[] KMP_GET(String grope) {
        int Begin = 0;
        int Length = grope.length();
        int[] pi = new int[Length];
        Arrays.fill(pi, 0);

        for (int i = 1; i < Length; i++) {
            while (grope.charAt(i) != grope.charAt(Begin) && Begin > 0) {
                Begin = pi[Begin - 1];
            }
            if (grope.charAt(i) == grope.charAt(Begin)) {
                pi[i] = ++Begin;
            }
        }
        return pi;
    }

    public static void main(String[] args) {
        String grope = "ABABCABAB";
        int[] result = KMP_GET(grope);
        System.out.println(Arrays.toString(result)); 
        // 출력: [0, 0, 1, 2, 0, 1, 2, 3, 4]
    }
}

그렇다면 이러한 내용이 전체적으로 적용된 문제를 통해 실질적인 코드와 여기서 보이어-무어를 사용한 코드까지를 보도록 하자.

문제 예시로 알아보는 KMP

문제예시 : 백준-찾기

이 문제를 통해서 보이어-무어 시간 복잡도와 KMP 시간 복잡도를 비교 분석해 보자.

우선 시간 복잡도 개념을 짚고 넘어갈 필요가 있는데, 보이어 무어는 평균적으로 빠르다.
즉 현실세계 또는 특수한 목적으로 만들어진 경우 유용하다. 하지만 최악의 경우
KMP 알고리즘 보다 못한 성능을 보일 수 있다.이해하고 넘어가 보자.

빅오(BigO)	KMP알고리즘	보이어-무어 알고리즘
최악	O(N+M)	O(N*M)
평균	O(N+M)	O(N/M)

이 문제의 KMP 알고리즘 코드와
보이어 무어 알고리즘 두 문제를 다 보도록 하자!

첫 번째는 KMP 알고리즘을 이용한 구현이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;

public class Main{
    static int cnt = 0;
    static List<Integer> li;
    static int[] getPi(String pattern){
        int size = pattern.length();
        int[] pi = new int[size];
        int j = 0;
        for(int i = 1; i < size; i++){
            while(j > 0 && pattern.charAt(i) != pattern.charAt(j)){
                j = pi[j - 1];
            }
            if(pattern.charAt(i) == pattern.charAt(j)) pi[i] = ++j;
        }
        return pi;
    }
    private static void KMP(String origin, String pattern){
        int pi[] = getPi(pattern);
        int j = 0;
        for(int i = 0; i < origin.length(); i++){
            while(j > 0 && origin.charAt(i) != pattern.charAt(j)){
                j = pi[j - 1];
            }
            if(origin.charAt(i) == pattern.charAt(j)){
                if(j == pattern.length() - 1){
                    ++cnt;
                    li.add(i - j + 1);
                    j = pi[j];
                }
                else j++;
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine();
        String pattern = br.readLine();
        li = new ArrayList<>();
        KMP(origin, pattern);
        System.out.println(cnt);
        for(int i = 0; i < cnt; i++){
            System.out.println(li.get(i));
        }
    }
}

두 번째는 보이어-무어 알고리즘을 이용했다. 이 경우 메모리 초과를 반환한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;

public class Main {
    static int cnt = 0;
    static List<Integer> li;

    private static int[] getBadCharacterShift(String pattern) {
        int[] badCharacterShift = new int[256];
        for (int i = 0; i < badCharacterShift.length; i++) {
            badCharacterShift[i] = pattern.length();
        }
        for (int i = 0; i < pattern.length() - 1; i++) {
            badCharacterShift[(int) pattern.charAt(i)] = pattern.length() - i - 1;
        }
        return badCharacterShift;
    }

    private static void BoyerMoore(String origin, String pattern) {
        int[] badCharacterShift = getBadCharacterShift(pattern);
        int offset = 0;

        while (offset <= (origin.length() - pattern.length())) {
            int j = pattern.length() - 1;

            while (j >= 0 && pattern.charAt(j) == origin.charAt(offset + j)) {
                j--;
            }

            if (j < 0) {
                li.add(offset + 1);
                cnt++;
                offset += (offset + pattern.length() < origin.length()) ? pattern.length() - badCharacterShift[origin.charAt(offset + pattern.length())] : 1;
            } else {
                offset += Math.max(1, j - badCharacterShift[origin.charAt(offset + j)]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine();
        String pattern = br.readLine();
        li = new ArrayList<>();
        BoyerMoore(origin, pattern);
        System.out.println(cnt);
        for (int i = 0; i < cnt; i++) {
            System.out.println(li.get(i));
        }
    }
}

그렇다면 이런 최악의 경우는 어떤 경우를 말하는 걸까?

해당 예시도 가져왔다.

보이어-무어(Boyer-Moore) 알고리즘의 최악의 경우는 
텍스트와 패턴이 특정한 방식으로 구성되어 있을 때 발생. 
이러한 상황은 텍스트와 패턴이 알고리즘의 효율성을 저하시키는 방식으로 배열된 경우 발생.

예를 들어, 패턴이 모든 문자가 동일.
텍스트가 패턴과 동일한 문자로 구성되어 있지만 마지막 문자가 다른 경우 `최악의 시나리오`

예시
텍스트: "AAAAAAAAAB"
패턴: "AAAAA"

이 경우, 보이어-무어 알고리즘은 
패턴의 마지막 문자에서 불일치를 발견할 때마다 패턴을 오른쪽으로 한 칸씩만 이동
따라서 텍스트의 모든 위치에서 패턴을 비교해야 하므로, 이 경우의 시간 복잡도는 O(N⋅M).

P.S. N과 M 은 위에서도 한 번 언급했지만 N(전체 문자열 길이), M(패턴 문자열 길이)를 뜻한다.

이러한 엣지케이스를 이해하고 있으면 어디서 문제가 생기는지 인지할 수 있고 이러한 경우가 들어갈 수 있다면 보이어-무어 사용을 재고해 볼 필요가 있다!

Outro

이렇게 예시를 통해 간단하게 전체적인 내용을 훑어 보았다. 알고리즘에 대한 깊이 있는 이해를 하기 위해 개념 학습을 더 하고 구현에 관해 알아가는게 재밌고 신기한 것 같다.

다음에는 보이어-무어 알고리즘의 good, bad 라는 내용으로 정리를 하며 문자열 검색 알고리즘에 관해 더 알아 보고, 정렬의 기본이 되는 삽입, 버블, 선택 정렬의 구현도 알아 볼 예정이다 :)