16916번 - 부분문자열(KMP 알고리즘, 실패함수)

16916번: 부분 문자열 (acmicpc.net)

골드 4티어 문제이며, 문자열 P 가 문자열 S의 부분문자열인지 알아보는 문제이다.

처음에는 일단 직관대로 문제를 풀어보았으나 시간 초과가 되었다.

.Java에서 지원하는 contains를 이용한 풀이이다.

public class 부분문자열_16916번_시간초과 {
    static String S, P;

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

        if (S.contains(P)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

 

두번째는 queue를 이용해 문자열 S를 미리 저장해놓고,
문자열 P의 시작 문자와 queue에 저장된 문자들을 비교해 나가며, P와 동일한 문자열을 찾는 방법을 사용했다.

하지만 아직도 시간초과가 나왔다.

public class 부분문자열_16916번_시간초과 {
    static String S, P;
    static int sLen, pLen;
    static char pStart;

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

        sLen = S.length();
        pLen = P.length();

        pStart = P.charAt(0);

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < S.length(); i++) {
            if (pStart == S.charAt(i)) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int start = queue.poll();
            if (start + pLen > sLen) {
                System.out.println(0);
                System.exit(0);
            }

            if (S.substring(start, start+pLen).equals(P)) {
                System.out.println(1);
                System.exit(0);
            }
        }

        System.out.println(0);
    }
}

 

더이상 고민하기에는 시간이 이미 많이 소요되어 다른 풀이들을 참고했다.

그 중 가장 이해하기 쉬웠던 글은 다음 글이였고 이를 참고했다.

[알고리즘] 문자열 검색 알고리즘 KMP 자바 구현하기 (백준 16916) (tistory.com)

아래 블로그는 실패함수를 이해하는데 도움을 받은 블로그이다.

[알고리즘] KMP 알고리즘 (tistory.com)

 

위 블로그에 기반하여 내가 이해한 KMP 알고리즘에 대해 정리해보자면 다음과 같다.

KMP알고리즘이란 문자열 매칭 검색 시 접두사와 접미사를 활용하여 중복 연산을 줄여나가 O(S + P)의 속도로 연산하는 기법이다.

이때 pi 배열을 구할 수 있는데, pi 배열이란 쉽게말해 문자열의 앞뒤가 같은 부분이다. ex)ABCDEAB = pi 배열의 길이 2

이렇게 pi 배열을 구하고 해당 배열을 이용해 비교를 진행하면 빠르게 연산할 수 있다는 말이다.

하지만 이렇게만 말하면 너무 난해하니, 아래 코드에서 설명하도록 하겠다.

내가 예시로 사용한 문자는 다음과 같다.

 

1. 패턴 분석

실패함수라는 개념을 이용해야 한다. 접두사와 접미사를 구분할 때, 이를 실사용 할 수 있도록 해야한다.

아래는 실패함수를 만드는 코드이다.

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

    int index = 0;
    for(int i = 1; i < pLen; i++) { // index 와 i의 시작점을 다르게 해준다.
        /*
        table = [ 0 ] [ 0 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 2 ] [ 3 ]   [ 2 ]
                  0     1     2     3     4     5     6     7       8
                  A     B     A     C     A     A     B     A       B
        * index가 0보다 크다는 것은 접두, 접미사 관계가 있었다는 것
        * 하지만 index에 위치한 문자와 i에 위치한 문자가 다르면, 더이상 같지 않다는 것이다.
        * 위 예시에서 마지막 문자 B를 상상해보자.
        * 그 동안(ABA) 반복되던 패턴의 끝 table[2]로 간다.
        * table 2에서는 하나가 반복되고 있단 의미의 1이 저장되어 있다.
        * table[index] == table[i]가 B == B로 만족하게 되며 아래 반복문으로 넘어가게 된다.
        * */
        while(index > 0 && pattern.charAt(i) != pattern.charAt(index)) {
            index = table[index - 1];
        }

        if(pattern.charAt(i) == pattern.charAt(index)) {
            index += 1; // 일치하는 문자가 있을 때 index는 증가한다.
            table[i] = index;
        } // 만일 index에 위치한 문자와 i에 위치한 문자가 같으면 table[i]에 index를 넣어준다.
    }
}

 

 

2. pi 배열 구하기

굳이 순번을 왜 저장해야 할까 라는 질문은 다음 코드를 보면 알 수 있다.

public static int search(String str, String pattern) {
    int sLen = str.length();
    int pLen = pattern.length();

    int index = 0;
    for(int i = 0; i < sLen; i++) {
        /*
        * 아래서 설명하는 바와 같이 실패함수를 이용한 방식
        * table[]을 더이상 갱신하지 않고, 이용해주기만 한다.
        * 이로써 패턴 분석이 가능해지고, 중복 검사를 획기적으로 줄일 수 있다.*/
        while(index > 0 && str.charAt(i) != pattern.charAt(index)) {
            index = table[index - 1];
        }

        if(str.charAt(i) == pattern.charAt(index)) {

            if(index == pLen - 1) { // 같은 숫자의 문자열이 일치한다는 뜻
                return 1;
            }
            else {
                index++;
            }
        }
    }
    return 0;
}

그래도 잘 모르겠을 수 있으니(나같은사람,,,) 아래 주석과는 다른 예시를 들어보겠다.

 

문자열 : ABABABCAABAB

패턴    : ABABCAABAB

 

마지막 파란부분이 정답이며, 배경색이 있는 부분이 pi 배열이다.

 

실패함수는 마지막에서 제대로 된 역할을 하게된다.

ABABABCAABAB

처음 ABAB가 나올 때까지는 index를 증가시키며 진행하고 있다.

이후 ABABA 라는 것을 알게 된 순간, 저장해놓은 실패함수를 이용한다.

실패함수를 이용하지 않았더라면 ABABA 3번째 A를 검사하고 있겠지만, 
실패함수 table[] 배열에 저장되어 있던 값으로 인해 ABABA  5번째 A 부터 시작할 수 있게 된다.

 

설명이 잘 되지 않았을수도 있지만, 위 과정을 이해했다면, pi 배열이 길어질수록, 실패함수는 그 의미가 커질 것이고,

엄청난 시간 단축을 이뤄낼 수 있다는 것을 공감할 것이다.

 

아래는 전체 코드이다.

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

public class 부분문자열_16916번 {
    static int[] table;

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

        String s = br.readLine();
        String p = br.readLine();

        makeTable(p);

        System.out.println(search(s, p));
    }

    public static int search(String str, String pattern) {
        int sLen = str.length();
        int pLen = pattern.length();

        int index = 0;
        for(int i = 0; i < sLen; i++) {
            /*
            * 아래서 설명하는 바와 같이 실패함수를 이용한 방식
            * table[]을 더이상 갱신하지 않고, 이용해주기만 한다.
            * 이로써 패턴 분석이 가능해지고, 중복 검사를 획기적으로 줄일 수 있다.*/
            while(index > 0 && str.charAt(i) != pattern.charAt(index)) {
                index = table[index - 1];
            }

            if(str.charAt(i) == pattern.charAt(index)) {

                if(index == pLen - 1) { // 같은 숫자의 문자열이 일치한다는 뜻
                    return 1;
                }
                else {
                    index++;
                }
            }
        }
        return 0;
    }

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

        int index = 0;
        for(int i = 1; i < pLen; i++) { // index 와 i의 시작점을 다르게 해준다.
            /*
            table = [ 0 ] [ 0 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 2 ] [ 3 ]   [ 2 ]
                      0     1     2     3     4     5     6     7       8
                      A     B     A     C     A     A     B     A       B
            * index가 0보다 크다는 것은 접두, 접미사 관계가 있었다는 것
            * 하지만 index에 위치한 문자와 i에 위치한 문자가 다르면, 더이상 같지 않다는 것이다.
            * 위 예시에서 마지막 문자 B를 상상해보자.
            * 그 동안(ABA) 반복되던 패턴의 끝 table[2]로 간다.
            * table 2에서는 하나가 반복되고 있단 의미의 1이 저장되어 있다.
            * table[index] == table[i]가 B == B로 만족하게 되며 아래 반복문으로 넘어가게 된다.
            * */
            while(index > 0 && pattern.charAt(i) != pattern.charAt(index)) {
                index = table[index - 1];
            }

            if(pattern.charAt(i) == pattern.charAt(index)) {
                index += 1; // 일치하는 문자가 있을 때 index는 증가한다.
                table[i] = index;
            } // 만일 index에 위치한 문자와 i에 위치한 문자가 같으면 table[i]에 index를 넣어준다.
        }
    }
}