알고리즘) KMP (Knuth–Morris–Pratt, 문자열 탐색 알고리즘)

KMP (Knuth–Morris–Pratt, 문자열 탐색 알고리즘)

기본적인 문자열 완전탐색 알고리즘에 비해, 약간의 메모리공간을 이용해 불필요한 비교횟수를 줄여 시간복잡도를 줄인다.

예를 들어, samsamsung 문자열에서 samsamsong 문자열을 찾는다면
원래는 0번째 인덱스 s부터 시작하여 쭉 같은지 비교하다가 u가 다르므로 실패하고
이후 1번째 인덱스 a부터 다시 비교하기 시작해, 이땐 처음부터 다르므로 바로 실패,
이후 2번째 인덱스 m부터 ~... 방식으로 비교한다.
=> 이때 KMP를 사용하면, 맨처음 u가 달라서 실패한 상태에서
samsamsung의 sams와 samsamsong의 sams가 같다는 정보를 기억하고 있다.
(물론 결과적으론 비교가 실패하게 되겠지만) 위의 정보를 이용해, 1번째 인덱스 a가 아닌 7번째 인덱스 u부터 비교하기 시작하므로 비교과정이 훨씬 빠르고 효율적으로 진행된다.

목표

Input	Output
첫 줄에 문자열의 길이 N이 주어집니다. 두 번째 줄에 문자열 N이 주어집니다. 세 번째 줄에 해당 문자열에서 찾으려고 하는 패턴 문자열 M의 길이가 주어집니다. 네 번째 줄에 문자열 M이 주어집니다.	패턴 문자열이 존재하지 않을 경우{}, 존재할 경우 패턴 문자열의 시작 인덱스를 다음과 같이 출력하세요.
sample input	sample output
12 samsabsamsam 6 samsam	{6}

* 매치되는 문자열이 여러개라면 {@,@, ...} 형태로 출력

해결방법

prefix & suffix를 이용해, 탐색과정중 불일치를 발견하면 '이제까지 본 문자열'의 접미사를 '찾는 문자열'의 접두사로 취급하여, 불필요한 비교를 안하고 그다음 문자부터 비교한다.

먼저 접두사(prefix)와 접미사(suffix)는 다음과같은 문자열들을 의미한다.

이제 주어진 문자열에서 prefix=suffix인 구간을 구한다.
pi배열 : pi[i]는 문자열의 0~i 구간의 부분문자열에서 prefix=suffix인 문자 수 중 가장 큰 값이다.
("ssmss"면 공통인 s와 ss중 ss -> 2)

이제 samsabsamsam에서 samsam을 찾는다.

samsa​bsamsam에서 samsa까지는 일치한다. 그 다음 index=5에서 b 때문에 불일치가 발생한다.
우리는 samsa까지 일치했을때의 pi[4]값을 알고있으므로, 이를 이용해 samsa에서 접미사 sa를 접두사로 만들어준다.
=> 구체적으로, match된 길이를 matched로 두고 matched-pi[matched-1]를 시작점으로 세팅,
matched는 pi[matched-1]로 세팅하면 다음과 같이 된다.

파란 시작점이 index 0 -> 3으로, 매치되어 비교중인 빨간 지점이 index 5 -> 5로 바뀜.
물론 곧바로 index 5에서 b때문에 불일치가 또 일어남. 이때는 pi값이 0이므로 matched=0이 되고 index 6부터 다시 탐색한다.

코드

pi배열을 구하고 kmp 알고리즘을 수행한다.

import java.util.*;

public class Test {
    static int n, m;
    static String N, M;

    static ArrayList<Integer> getPartialMatch(String M) {
        int m = M.length();
        ArrayList<Integer> pi = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            pi.add(0);
        }

        int begin = 1, matched = 0;
        while (begin + matched < m) { // kmp로직과 약간 비슷한 방식으로 pi를 구함
            if (M.charAt(begin  + matched) == M.charAt(matched)) {
                ++matched;
                pi.set(begin + matched - 1, Integer.valueOf(matched));
            } else {
                if (matched == 0)
                    ++begin;
                else {
                    begin += matched - pi.get(matched - 1);
                    matched = pi.get(matched - 1);
                }
            }
        }
        return pi;
    }

    static Vector<Integer> kmpSearch(String N, String M) { // kmp로직대로 동작
        ArrayList<Integer> pi = getPartialMatch(M);
        Vector<Integer> ret = new Vector<>();
        int n = N.length(), m = M.length();
        int begin = 0, matched = 0;
        while (begin <= n - m) {
            if (matched < m && N.charAt(begin + matched) == M.charAt(matched)) {
                ++matched;
                if (matched == m) {
                    ret.addElement(begin);
                }
            } else {
                if (matched == 0) {
                    ++begin;
                } else {
                    begin += matched - pi.get(matched - 1);
                    matched = pi.get(matched - 1);
                }
            }
        }
        return ret;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // not used
        N = scanner.next();
        m = scanner.nextInt(); // not used
        M = scanner.next();
        Vector<Integer> sol = kmpSearch(N, M);
        System.out.print("{");
        for (int i = 0; i < sol.size() - 1; i++) {
            System.out.print(String.valueOf(sol.elementAt(i)) + ",");
        }
        if (!sol.isEmpty()) {
            System.out.print(String.valueOf(sol.lastElement()));
        }
        System.out.print("}");
    }
}