[백준 / BOJ] 16916 부분 문자열 (Java)

문제

출처 : https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

문자열 S, 문자열 P가 주어진다. 

문자열 P가 문자열 S에 속하는지 확인하는 문제다.

 

---

풀이

KMP알고리즘을 이용해 푸는 문제다.

문자열의 길이가 최대 100만까지 증가하기때문에, KMP알고리즘을 이용해 풀어야한다.

 

(suffix배열을 만들지 못하는 문자열에서 여전히 시간초과가 나올것이라 생각했는데, 다행히? 그런 테스트케이스는 없는것 같다.)

 

로직

1. 문자열 P가 S에 포함되는지 확인해야하기 때문에,  문자열 P를 갖고 suffix 배열을 만든다.

2. 만들어진 배열을 갖고 KMP알고리즘을 수행하면 답.

 

소스코드

 

KMP

    private int doKmp(String target, String str){
        int strIdx = 0;
        for(int targetIdx = 0; targetIdx < target.length(); targetIdx++){
            while(target.charAt(targetIdx) != str.charAt(strIdx) && strIdx > 0) strIdx = pi[strIdx-1];
            if(str.charAt(strIdx) == target.charAt(targetIdx)) strIdx++;
            if(strIdx >= str.length()) return 1;
        }
        return 0;
    }

 

suffix array

    private int[] setPi(String str){
        int[] ret = new int[str.length()+5];
        int pIdx = 0;
        for(int i = 1; i < str.length(); i++){
            while(str.charAt(i) != str.charAt(pIdx) && pIdx > 0) pIdx = ret[pIdx-1];
            if(str.charAt(i) == str.charAt(pIdx)){
                pIdx++;
                ret[i] = pIdx;
            }
        }
        return ret;
    }

 

KMP알고리즘은 생각을 구현으로 옮기는게 어려웠는데 이번에는 비교적 빠르고 깔끔하게 구현된것 같다.

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/16916%20%EB%B6%80%EB%B6%84%20%EB%AC%B8%EC%9E%90%EC%97%B4/Main.java

devxb/JJUNalgo