h.o.Algorithm | Java | 백준 16916 - 문자열 포함 판독 KMP 알고리즘

백준 16916 문제를 해결하는 과정에서 사용한 KMP 알고리즘에 대한 기록이다.

h.o.Algorithm - Java 백준 16916

h.o.Algorithm - KMP 알고리즘 - 문자열 포함 판독

문제

두 개의 문자열이 주어진다. 두 번째 문자열이 첫 번째 문자열에 포함되는지 여부를 판단하는 문제이다.

풀이

String.contins()를 이용한 풀이

간단하게 String.contains() 메소드를 이용해서 문제를 해결을 시도하였다.

import java.io.*;

public class baekjoon16916 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String REF = br.readLine();
        String tester = br.readLine();
        if(REF.contains(tester)){
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

 

하지만 결과는 시간초과이다.

분석

contains()는 내부적으로 indexOf(), 즉 반복문을 사용해 문자열 검색을 수행한다. 문자열 하나당 패턴 문자열 전체를 탐색하기 때문에 문자열 N과 패턴 문자열 M이 주어질 경우 시간복잡도가 O(N*M)을 갖는다.

새로운 풀이

KMP (Knuth-Morris-Pratt) 알고리즘을 이용한 풀이

KMP 알고리즘은 패턴 문자열의 패턴 정보를 배열에 넣어두고, 미리 파악해 높은 패턴 정보를 활용해 문자열 포함을 확인하는 재미있는 알고리즘이다. 살짝 복잡할 수 있지만 패터닝과정과, 패터닝 이후 일치하는 패턴을 찾는 로직이 거의 비슷하기 때문에 한 번만 잘 이해하면 잘 사용할 수 있을 것이다.

패터닝

먼저 패터닝 알고리즘을 먼저 살펴보자. 패턴 텍스트만을 사용해 패턴 정보를 하나의 배열에 담는 과정이다.

private static int[] computePi(String pattern){
    int m = pattern.length();
    int[] pi = new int[m];
    int j = 0;

    for(int i=1; i<m; 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;
}

패턴 길이의 배열을 하나 생성해 준다. j는 패턴을 추적할 인덱스이고, for 문의 i는 패턴 전체를 순서대로 추적할 인덱스 이다. 이 두 인덱스가 가리키는 문자가 같을 경우 배열에 j+1 값을 담아주고, 해당 문자부터 일치하는 문자까지 j 값을 늘려 가며 배열에 담아준다.

예) 문자열 3개가 일치하면 배열에 해당 i 번째 위치에서부터 1, 2, 3가 할당된다.

이렇게 추적해 가다가 일치하지 않는 문자가 나타나면 j 값을 배열의 j-1 번째 값으로 재설정 해준다. 이 때 j는 실제 일치한 패턴의 수이고, j-1은 배열은 0부터 센다는 걸 생각하면 기억하기 쉽다.

텍스트와 패턴 비교

이제 작성한 패턴 배열 정보를 이용해 텍스트와 패턴을 비교하는 과정을 살펴보자.

private static boolean kmp(String text, String pattern){
    int[] pi = computePi(pattern);
    int n = text.length();
    int m = pattern.length();
    int j =0;

    for(int i=0; i<n; i++){
        while(j>0 && text.charAt(i) != pattern.charAt(j)){
            j = pi[j-1];
        }
        if(text.charAt(i) == pattern.charAt(j)){
            if(j == m-1){
                return true;
            }
            j++;
        }
    }
    return false;
}

패터닝 과정과의 차이점은 같은 문자를 가리킬 때 현재 j값이 패턴 배열의 마지막 인덱스 값인지 확인하는 것이다. j값이 패턴 배열의 마지막 인덱스에 도달했다는 것은 패턴 문자열이 모두 텍스트에 포함되었다는 의미이다.

전체 코드

import java.io.*;

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

        if(kmp(REF, tester)){
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static boolean kmp(String text, String pattern){
        int[] pi = computePi(pattern);
        int n = text.length();
        int m = pattern.length();
        int j =0;

        for(int i=0; i<n; i++){
            while(j>0 && text.charAt(i) != pattern.charAt(j)){
                j = pi[j-1];
            }
            if(text.charAt(i) == pattern.charAt(j)){
                if(j == m-1){
                    return true;
                }
                j++;
            }
        }
        return false;
    }

    private static int[] computePi(String pattern){
        int m = pattern.length();
        int[] pi = new int[m];
        int j = 0;

        for(int i=1; i<m; 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;
    }
}

해당 코드 정보는 아래 GitHub 링크에서도 확인할 수 있다.

Study/Java/DataStructureAlgorithm/src/알고리즘문제풀이/문자열/baekjoon16916.java at main · YdMinS/Study

분석

• 패터닝 시간복잡도

패터닝 과정은 길이가 M인 패턴 텍스트를 한 번 순회하기 때문에 O(M)이다.

• 텍스트와 패턴 비교과정 시간 복잡도

텍스트 비교 과정에서 길이가 N인 텍스트를 최대 한 번 순회하기 때문에 O(N)이다.

• 전체 시간복잡도

전체 시간복잡도는 O(N) + O(M) ~ O(N)이다. contains()의 O(N*M)~(M^2)와 비교할 때 상당한 차이가 있는 것을 볼 수 있다.