KMP 알고리즘 (with 백준 1786)

• KMP 알고리즘

KMP알고리즘이란 문자열 "ABCABCD"가 있을때 그 안에서 문자열 "ABCD"를 찾는 알고리즘이다.

우리가 잘 알고있는 브루트포스로도 찾을 수 있지만 브루트포스는 ABCABCD에서 ABCD를 찾을때 다음과 같이 비효율 적으로 탐색을 한다.

(1)

ABCABCD

ABCD

 

(2)

ABCABCD

AABCD

 

(3)

ABCABCD

AAABCD

(4)

ABCABCD

AAAABCD

 

하지만 우리는 (1)에서 첫번째 문자가 'A', 두번쨰 문자가 'B', 세번째 문자가 'C'라는 것을 탐색을 통해 알았기에 굳이 (2), (3)의 경우를 탐색할 필요없이 (4)로 넘어가도 된다. 즉 우리가 탐색한 부분의 정보를 최대한 효율적으로 이용하자는 말이다. 굳이 탐색했던 'B', 'C'를 다시 탐색할 필요 없이 바로 (4)로 넘어가게 해주는 것이 KMP알고리즘이다. 실제로 문자 수가 n이고 찾으려는 패턴의 문자 수가 m일때 문자열 검색시 시간복잡도는 브루트포스가 O(mn)이고 KMP가 O(n)이다. 

 

 우선 우리는 KMP알고리즘을 위해 Table을 만들 것이다. Table을 설명하기 위해 주어진 문자열을 dest라하고 dest 안에서 찾을 문자열을 find라 하겠다. dest = "ABABABAABAB"이고 find = "ABAABAB"일때의 Table을 만들어보자.

  Table은 int형 배열로 만들 것인데 Table[j -1] = 'j개까지만 문자가 같았을 때 다음 비교시 find의 탐색 시작 index' 라 보면 된다.

 Table에는 find를 앞에서 부터 1글자씩 늘려가며 접두사와 접미사가 같은 경우 그 문자들의 개수를 넣을 것이다.

 현재 find인 "ABAABAB"를 기준으로 보면 다음과 같다.

(1) :  A           > Table[0] = 0

(2) :  AB        > Table[1] = 0

(3) :  ABA          > Table[2] = 1

(4) :  ABAA        > Table[3] = 1

(5) :  ABAAB       -> Table[4] = 2

(6) :  ABAABA       -> Table[5] = 3

(6) :  ABAABAB       -> Table[5] = 2

 

이렇게 눈으로 보는 Table 만들기는 쉽지만 실제 코드로 구현해보면 생각보다 이해가 쉽지 않다. 그리고 코드를 보면 알겠지만 KMP를 위한 Table을 만들면서 KMP를 사용하고 있다. (find를 통해 find의 Table을 만듦)

static int[] make_table(String find)
{
    int[] table = new int[find.length()];
    int j = 0;
    for (int i = 1; i < find.length(); i++)
    {
        while (j > 0 && find.charAt(i) != find.charAt(j))
            j = table[j - 1];
        if (find.charAt(i) == find.charAt(j))
            table[i] = ++j;
    }
    return (table);
}

다음과 같이 만드는데 for 문을통해 j = 0부터, i = 1 부터 위의 조건을 통해 Table[i]를 작성한다. (Table[0] 은 무조건 0이므로 i = 1부터 시작한다. 그리고 j가 접두사를 탐색하고 i는 접미사를 탐색해서 find의 접두사와 접미사의 공통부분의 개수를 찾는다)

 크게 보면 KMP를 이용해 굳이 재탐색을 하지 않으면서 Table을 채우는 코드로 밑에 if 문은 두 문자가 같을 경우라 치고 어느정도 이해가 되는데 while문 내용이 이해하기 좀 어렵다. 

 while 문의 내용은 브루트포스처럼 탐색한 곳을 재탐색 하지 않기 위해 밟는 절차라 생각하면 된다. 만약 문자가 서로 다른 것이 발견된 경우 브루트포스라면 i를 탐색했었던 이전 지점으로 돌리고 j를 0부터 다시 탐색을 시작했을 것이다. 하지만 KMP에서는 j > 0 이고 비교하는 문자가 서로 다를경우 지금까지 접두사와 접미사가 j개까지는 같았고 j + 1개째에서 틀렸으므로 j개의 문자가 같았을 경우 find의 다음 비교 시작점을 j에 대입을 하여( j = Table[j - 1] ) 다시 dest의 i번째 index와 비교를 해보고 이를 j == 0까지 반복해서 같은 문자가 나오지 않는다면 i = i + 1을 하여 j = 0부터 다시 탐색을 시작하는 것이다.

 위 내용을 이해하면 KMP는 거의 다 이해한것이다. 물론 내용이 너무 어려워서 글로 설명이 충분히 안됐을 것 같으니 코드를 혼자 적어보며 최대한 이해했으면 좋겠다.

static int KMP(String dest, String find)
{
    int[] table = make_table(find);
    int j = 0;
    for (int i = 0; i < dest.length(); i++)
    {
        while (j > 0 && dest.charAt(i) != find.charAt(j))
            j = table[j - 1];
        if (dest.charAt(i) == find.charAt(j))
        {
            if (j == find.length() - 1)
                return (i - j);
            else
                j++;
        }
    }
    return (-1);
}

 위 Table을 가지고 Table을 만든 방법으로 KMP알고리즘을 다시 다음과 같이 돌린다.

아까 Table을 만들때와 많이 다르지 않다. 이번에는 i와 j 모두 0에서 시작을 하고 dest의 i번째 문자와 find의 j번째 문자를 비교하면서 같으면 i와 j를 +1 해주고 다르면 j개의 문자는 같았으므로 j = table[j - 1]을 통해 j개의 문자가 같았을 경우 다음 find의 시작 index인 j를  Table을 통해 바꿔주면서 계속 비교를 해준다. 그리고 만약 j == find.length() - 1이 될 경우, 즉 find를 dest에서 찾은 경우 그 시작 index인 i - j를 반환한다. 하지만 i == dest.length()에 다달아서 dest안에 find를 찾지 못한 경우는 -1을 반환한다. 

 

정말 어려운 알고리즘이라 정말 최선을 다해 설명을 적었지만 이해가 될 수 있는 설명인지는 잘 모르겠다. 하지만 그만큼 어려운 알고리즘이므로 쉽게 얻을 생각을 하지 않고 계속 반복을 해서 내것으로 만들어야 겠다.

 

다음은 백준의 KMP를 이용한 문제이다. 백준 1786번 찾기  >> https://www.acmicpc.net/problem/1786

1786번: 찾기

이 문제는 dest안에서 find가 몇개 있고 그 find들의 위치를 나타내야하는 문제이다. 딱 봐도 KMP를 이용하는 문제인데 우리가 위에서 본 코드에서 find를 여러개 찾는다는 점만 다르다. 그러면 코드를 보고 이해해보자.

import java.io.*;
class Main {
    static int num = 0;
    static StringBuilder sb = new StringBuilder();
    static int[] make_table(String find)
    {
        int[] table = new int[find.length()];
        int j = 0;
        for (int i = 1; i < find.length(); i++)
        {
            while (j > 0 && find.charAt(i) != find.charAt(j))
                j = table[j - 1];
            if (find.charAt(i) == find.charAt(j))
                table[i] = ++j;
        }
        return (table);
    }

    static void KMP(String dest, String find)
    {
        int[] table = make_table(find);
        int j = 0;
        for (int i = 0; i < dest.length(); i++)
        {
            while (j > 0 && dest.charAt(i) != find.charAt(j))
                j = table[j - 1];
            if (dest.charAt(i) == find.charAt(j))
            {
                if (j == find.length() - 1)
                {
                    num++;
                    sb.append(i - j + 1).append(' ');
                    // j = table[j]로 써도 되지만 이해를 위해 다음과 같이 작성
                    j++
                    j = table[j - 1];
                }
                else
                    j++;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String dest = br.readLine();
        String find = br.readLine();
        KMP(dest, find);
        System.out.println(num);
        System.out.println(sb);
    }
}

 

찾기 문제에서는 KMP를 그대로 가져다 쓰는것이 아닌 알고리즘을 완벽히 이해를 해서 응용을 할 수 있어야했다. 알고리즘에서 가장 어려운 부분인 문자가 다를 경우 다음 j를 선택하는 법을 잘 이해 했어야 하고 그 부분을 이해했다면 dest에서 find가 여러개 나온경우를 찾을 수 있게 된다.

 그 부분이 바로 주석 밑에 부분인데 dest에서 find를 찾은 경우 계속 탐색을 하기 위해 dest의 다음 i번째 문자와 find의 몇번째 index를 비교해야 하는지가 중요하다. 위에서 j개의 문자가 같은 경우 j + 1번쨰 문자가 달라서 find의 다음 시작점을 찾아야 한다면 그 index인 j = Table[j - 1]가 된다고 정의를 했었다. 따라서 이를 문제에 적용해보면 find를 찾은 경우 j++를 해줘 j를 find의 문자 길이와 같게 만든다. 그러면 현재 find의 문자의 개수인 j개의 문자가 같은 경우라 할 수 있고 다음 j의 시작점을 j = table[j - 1]로 정의할 수 있다. (find를 찾았고 다음 find를 찾아야하므로 j + 1번째 문자가 다르다 하고 다음 find를 찾기위해 새로운 시작점 j를 찾는 것!)

 

마지막으로 이것만 외우자 !! 

Table[j -1] = 'j개까지만 문자가 같았을 때 다음 비교시 find의 탐색 시작 index'

 

---

reference

 -https://devje8.tistory.com/24