KMP -JAVA

KMP Algorithm : 문자열 검색 알고리즘

💡 **특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘. 워드 파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다.**

1. 단순 문자열 알고리즘

가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다.

• 검색할 문자열 : ABDEGH
• 찾는 문자열 : DE

가장 앞 부분부터 찾는 문자열이 매칭될 때까지 탐색을 시작한다.

매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다.

매칭이 이루어졌으면 탐색을 종료한다.

위와 같은 예시가 아닌, “A B A C A A B A”를 검색하는 패턴이 “A B A C A B”인 경우에서는, 불필요한 연산이 다시 진행되는 경우도 있다. 이 때, 단순히 틀린 위치부터 탐색하면 되지 않을까? 라고 생각할 수 있다.

 

하지만, 주어진 문자열의 3번째 위치에 A가 다시 등장하고, 패턴의 시작 부분도 A이기 때문에 다른 경우에서 정답이 존재할 수 있으므로 해당 위치의 탐색을 스킵하면 안된다.

따라서 접두사와 접미사를 활용하여 확실한 중복 연산들을 판별하여 줄여나가며 연산할 수 있는 KMP 알고리즘을 사용한다.

소스코드

이 알고리즘은 이중 반복문으로 시간 복잡도는 $O(N*M)$이 된다. 효율적이지는 않지만 코드가 직관적이라서 간단하게 사용하기 좋다.

// 1. 단순 문자열 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SimpleStringMatching {

    public static int findString(String parent, String pattern) {
        int n1 = parent.length();
        int n2 = pattern.length();

        for (int i = 0; i <= n1 - n2; i++) {
            boolean flag = true; // 문자열이 일치하는 지 체크하는 boolean형 변수

            for (int j = 0; j < n2; j++) {
                // 문자열이 일치하지 않은 경우, flag 값을 false로 변경 후 반복문 종료
                if (parent.charAt(i + j) != pattern.charAt(j)) {
                    flag = false;
                    break;
                }
            }

            // 이중 반복문에서 j를 통해 문자열을 확인할 때마다 수행
            if (flag) {
                return 1; // 문자열을 찾으면 1을 반환
            }
            // 문자열을 찾지 못한 경우, 다음 i 인덱스에서 반복문을 재수행
        }
        return 0; // 문자열을 찾지 못하고 반복문을 종료한 경우 0을 반환
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s1 = br.readLine();
        String s2 = br.readLine();

        System.out.println(findString(s1, s2));
    }
}

2. KMP(Knuth-Morris-Pratt) 알고리즘

[알고리즘] KMP 알고리즘

[코딩 알고리즘] KMP 알고리즘

위와 같은 단순 문자열 매칭 알고리즘은 긴 문자열을 탐색할 경우 최악의 경우가 발생하면 엄청난 시간이 소요될 수 있다. 예를 들어 길이가 10,000,000인 글에서 길이가 1,000인 부분의 문자열을 찾으려는 경우, 연산 양이 10,000,000,000(100억)이기 때문이다. 따라서 모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있는 KMP 문자열 매칭 알고리즘을 사용해야 한다.

 

KMP는 접두사와 접미사의 개념을 활용하여 모든 경우를 계산하지 않고 반복되는 중복 연산을 줄여나가 매칭 문자열을 빠르게 점프하는 기법으로 효율적으로 문자열 매칭을 이루어나간다. 따라서 KMP 알고리즘의 시간 복잡도는 $O(N+M)$이다. (N : 텍스트의 길이, M : 패턴의 길이)

여기서 접두사와 접미사란, A B A C A A B A 란 문자열이 있을 때,

접두사 : A, AB, ABA, ABAC … 처럼 앞에서 하나씩 끊어서 본 것을 뜻하고

접미사 : A, BA, ABA, AABA … 처럼 뒤에서 하나씩 끊어서 본 것을 뜻한다.

위를 바탕으로 table 배열을 구할 수 있다.

 

table 배열 : 부분 문자열 중에서 접두사 == 접미사가 될 수 있는 가장 긴 것의 길이

KMP 알고리즘을 동작시키기 위해서는 접두사도 되고 접미사도 되는 문자열의 최대 길이를 저장해주는 table을 미리 정의해줘야 한다. table[]은 pattern이 어디까지 일치했는 지가 주어질 때 다음 시작 위치를 어디로 해야할 지를 말해주기 때문에, 이를 흔히 부분 일치 테이블이라고 부른다.

→ table[i] = pattern(0…i)의 접두사도 되고 접미사도 되는 문자열의 최대 길이

예를 들어, abacaaba가 있을 때 다음과 같다.

일치하는 접두사와 접미사의 최대 길이는 aba로 3이다. 해당 탐색한 결과를 table[] 배열에 저장하면 다음과 같이 저장된다.

접두사와 접미사가 일치하는 최대 길이를 구한 부분 일치 테이블을 구했다면 이후 동작 과정은 간단하다. 이제 table 배열을 이용하여 parent 문자열과 pattern 문자열을 index = 0 부터 비교해주면 된다.

3. KMP 알고리즘 탐색 과정

KMP 알고리즘은 접두사와 접미사가 일치하는 경우에 문자열 매칭을 탐색할 때 점프를 할 수 있어서 굉장히 효율적으로 작동하게 된다. 다음 예시를 살피며 이해해보자.

먼저 두 문자열을 비교하여 접두사와 접미사의 일치하는 최대의 길이를 찾아준다.

• 검색할 문자열(str) : ababacabacaaba
• 찾는 문자열(pattern) : abacaaba
• pattern 테이블의 값을 위에서 보였던 예시를 통해 아래의 그림과 같이 구해준 다음, 알고리즘을 수행한다.
• pattern table[] : [0, 0, 1, 0, 1, 1, 2, 3]
• 반복문의 범위 : 0 ~ parent.length() - 1

1. i=0, idx=0 → idx 1 증가

1. i=1, idx=1 → idx 1 증가

1. i=2, idx=2 → idx 1 증가

1. i=3, idx=3 → idx = table[idx-1] = table[2] = 1

 

1. i=4, idx=1 → idx 1 증가
2. → 이전 탐색에서 불일치 되어도 idx=1 부터 시작하는 이유는 pattern 접두사 a와 접미사 a가 일치하므로 idx=1(b) 부터 탐색하는 것이다. 이것이 KMP 알고리즘이 빠르게 동작하는 이유!

 

1. i=5, idx=2 → idx 1 증가
2. i=6, idx=3 → idx 1 증가

1. i=7, idx=5 → idx = table[idx-1] = table[4] = 1

1. i=8, idx=1
2. → (8)에서 불일치 되었으므로 다시 탐색을 시작한다. 이번에도 접두사 접미사 a가 일치하므로 탐색 idx=1(b)부터 재탐색을 시작한다.

1. i=9 ~ 13

위와 같이 끝까지 탐색을 수행했을 때, idx=7 (pattern.length() - 1)에 도달한다. 이는 문자열 탐색에 성공했다는 뜻이므로 탐색을 완료한다. (만약, 계속 탐색을 시도해야 하는 경우 idx=table[idx] 명령어를 통해 idx를 다시 돌려주면 된다.)

→ console 화면

4. KMP 알고리즘 구현 방식

1. idx > 0, parent의 i번째 문자 != find의 j(idx)번째 문자
   • idx = table[idx - 1];
   문자열 매칭이 시작된 후 연속적으로 매칭이 되지 않을 때 다시 매칭을 시작해야 하므로 idx 값을 다시 돌려준다. 그런데 만약 문자열 매칭된 부분이 접두사와 접미사가 같은 구간이라면 idx는 0이 아닌 그 일치하는 길이만큼의 값을 받게 된다. 그러므로 앞에 접두사 부분을 생략하고 다시 재빠르게 탐색이 가능해진다.
2. parent의 i번째 문자 == find의 j(idx)번째 문자
   • if (idx == find 문자열 길이 - 1) → 탐색 종료
   • else → idx값 1 증가
   idx값이 (find 문자열 길이 - 1) 까지 도달했다면 문자열 매칭을 성공한 것이므로 탐색을 종료한다. 아니면 일치할 때 마다 idx 값을 1 증가하여 다음 문자를 매칭하도록 한다.

• i = matched + begin, idx = matched 라고 생각하면 위와 동일

소스코드

/*
 * Input (1)
 * ABDEGH
 * DE
 * 
 * Output (1)
 * 3번째에서 찾았습니다.
 * 
 * Input (2)
 * ababacabacaabacaaba
 * abacaaba
 * 
 * Output (2)
 * 7번째에서 찾았습니다.
 * 12번째에서 찾았습니다.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class KMP {

    public static int[] makeTable(String pattern) {
        int pLen = pattern.length();
        int[] table = new int[pLen];

        int idx = 0;
        for (int i = 1; i < pLen; i++) {
            // idx > 0 : 문자열 매칭 시작
            // 연속으로 일치하지 않으면 idx 값을 돌려주어 다시 매칭 시작 (idx = table[idx - 1])
            while (idx > 0 && pattern.charAt(i) != pattern.charAt(idx)) {
                idx = table[idx - 1];
            }

            if (*pattern.charAt(i) == pattern.charAt(idx)) {
                table[i] = ++idx;*
            }
        }
        return table;
    }

    public static void KMP(String str, String pattern) {
        int[] table = makeTable(pattern);

        int sLen = str.length();
        int pLen = pattern.length();

        int idx = 0; // 현재 대응되는 글자 수
        for (int i = 0; i < sLen; i++) {
            System.out.println("i: " + i + ", " + "idx: " + idx); // 디버깅
            // idx번째 글자와 짚더미의 해당 글자가 불일치할 경우
            // 현재 대응된 글자의 수를 table[idx - 1]번으로 줄임
            while (idx > 0 && str.charAt(i) != pattern.charAt(idx)) {
                idx = table[idx - 1];
            }
            // 글자가 대응될 경우
            if (str.charAt(i) == pattern.charAt(idx)) {
                if (idx == pLen - 1) {
                    // parent 문자열과 pattern 문자열이 일치하기 시작한 시점을 출력
                    System.out.println(i - idx + 1 + "번째에서 찾았습니다.");
                    idx = table[idx];
                }
                else {
                    idx++;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s1 = br.readLine();
        String s2 = br.readLine();

        KMP(s1, s2);
    }
}

parent 문자열 : a b a b a c a a

pattern 문자열 : b a c

문제

KMP Algorithm

16916번: 부분 문자열

 

1786번: 찾기

→ 문제 내용 잘 읽기! (KMP 알고리즘에 탄생 배경과 내용에 대해 설명이 있음)