[백준] 16916 부분문자열

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

16916번: 부분 문자열

 

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

 

 

내풀이

브루탈포스로 시도... 당연하게 시간초과 남 

근데 문자열 관련 알고리즘은 머리에 입력된 적이 없었기에 당연하게 더 이상의 방법이 생각나지 않았다

검색해보니 Kmp 알고리즘을 적용하여 해결하면 된다고 하여 이를 이해하고 공부한 것을 정리하고자 한다.

 

참고 블로그

[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘 :: DDijkstra's Record (tistory.com)

[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘

 

 

Kmp 알고리즘의 기본적인 아이디어는 접두사와 접미사를 이용하여 불필요한 탐색횟수를 줄이는 것 입니다

예를 들어 ABABC 에서 ABC 를 찾는다면 AB 를 검사한후 A != C 인후 BABC에서 다시 탐색하는 것이 아닌 AB를 기억하고 ABC에서 탐색을 하는 것입니다. 

=> O (문자열 길이 + 패턴 길이) 시간복잡도로 수행할 수 있습니다

 

이를 구현하기 위해서는 패턴 문자열의 pi 배열 (부분 문자열에서 접두사와 접미사가 얼마나 일치하는지 저장하는 배열)을 이용합니다.

 

j 는 접두사의 위치, i 는 접미사의 위치

 

1.  j 와 i가 일치하는 경우  ( = 그 위치에서 접두사와 접미사가 일치했다는 것)
   
   1. 다음 위치의 j와 i의 문자도 일치하는지 검사 
   2. j 와 i 오른쪽으로 한칸 이동
2.  j 와 i 가 일치하지 않는 경우 ( = 접두사와 접미사가 일치하지 않다는 것 => 다시 검사해야 함)
   1.  지금까지 일치했던 곳에서 다시 탐색하는 것이 효율적 (다시 처음부터 탐색하면 브루탈 포스)
   2.  pi 배열을 이용하여 j = pi [ j - 1 ] 으로 이동 ( j - 1 까지는 접두사와 접미사가 일치했었으니깐)

 

이걸 배열에서의 동작을 다시 정리하면

 

j 는 맨 앞 ( = 0 ) 에서 시작, i 는 1부터 시작 

j 와 i 가 같다면 같이 1씩 증가 ( 접두사와 접미사가 일치하는 경우) , pi [ i ] = j + 1 로 위치 저장

같지 않다면  j = pi [ j - 1 ] 으로 이동

 

예시 : pi 배열 만드는 과정 

 

 

예시 : pi 배열 이용하여 탐색

 

 

 

 

소스 코드 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static String src = "baekjoon\n" +
            "baekjon";

    static int result, pi[];
    static String original, subStr;

    public static void main(String arg[]) throws IOException {
        //input= new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        original = input.readLine();
        subStr = input.readLine();

        pi = new int[subStr.length()];
        getPi();
        Kmp();

    }

    public static void Kmp() {
        int j = 0;
        for (int i = 0; i < original.length(); i++) {
            // 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
            while (j > 0 && original.charAt(i) != subStr.charAt(j)) {
                j = pi[j - 1];
            }
            // 맞는 경우
            if (original.charAt(i) == subStr.charAt(j)) {
                //부분 문자열 완성 => 탐색 종료
                if (j == subStr.length() - 1) {
                    result = 1;
                    break;
                }
                //맞았지만 패턴이 끝나지 않았다면 j를 하나 증가 
                // => i는 for문으로 차피 증가 ( i, j 같이 증가하는것)
                else{
                    j++;
                }
            }
        }
        System.out.println(result);
    }

    public static void getPi() {
        int j = 0;
        for (int i = 1; i < subStr.length(); i++) {
            // 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
            while (j > 0 && subStr.charAt(i) != subStr.charAt(j)) {
                j = pi[j - 1];
            }
            // 맞는 경우
            if (subStr.charAt(i) == subStr.charAt(j)) {
                //i길이 문자열의 공통 길이는 j의 위치 + 1
                pi[i] = ++j;
            }
        }
    }
}