BOJ-16916 부분 문자열

1. 문제

문제 링크 : https://www.acmicpc.net/problem/16916

알고리즘 분류 : 문자열, KMP

2. 고민

원래 문자열에 부분 문자열이 포함되어 있는지 찾는 문제이기 때문에

문자열 길이도 최대 100만이었고 완전 탐색으로 구현하면 O(N)으로 구할 수 있다고 생각했습니다.

그래서 다음과 같이 완전 탐색 알고리즘으로 구현해보았습니다.

3. 1차 시도 (실패)

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

    public class Main {
        
        static String origin, part;     // 원 문자열, 부분 문자열

        static boolean isSameStr() {    // 부분 문자열이 포함되어있는지 체크하는 메서드
            for(int idx=0; idx<origin.length()-part.length()+1; idx++) {
                if (origin.substring(idx, idx+part.length()).equals(part)) return true;
            }

            return false;
        }

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

            System.out.println(isSameStr() ? 1 : 0);
        }
    }

결과는 TLE였습니다….

분명, 반복문 하나인데 왜 TLE일까 곰곰히 생각을 해봤는데

equals 안을 뜯어보니 다음과 같이 반복문이 하나 더 있었습니다.

    public static boolean equals(byte[] value, byte[] other) {
        if (value.length == other.length) {
            int len = value.length >> 1;
            for (int i = 0; i < len; i++) {
                if (getChar(value, i) != getChar(other, i)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

알고보니 저는 O(N)으로 완전 탐색을 하고 있었던게 아닌 O(NM)으로 탐색하고 있었고,

100만 * 100만인 1조의 연산을 하고 있었던 것이었습니다.

그래서 방법이 없을까 인터넷 검색을 해봤더니 KMP 알고리즘이라는 것이 있었습니다.

KMP 알고리즘은 접두사와 접미사를 이용한 알고리즘인데

먼저 동일한 접두사와 접미사의 길이를 담은 pi배열을 만든 후,

원래 문자열에서 부분 문자열이 있는지 체크를 하는데

만약, 매칭 실패가 이루어졌다면

그 배열을 통해 한번에 뛰어넘어 부분 문자열을 빠르게 찾는 방법입니다.

이 알고리즘의 시간 복잡도는 O(N)입니다.

4. 2차 시도 (성공)

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

    public class Main {

        static char[] origin, pattern;      // 원 문자열, 부분 문자열
        static int[] table;                 // pi배열

        // 접두사와 접미사가 같은 부분 문자열 길이 배열 계산
        static void makeTable() {
            int len=0;
            for(int idx=1; idx<pattern.length; idx++) {
                while(len>0 && pattern[idx] != pattern[len])
                    len = table[len-1];

                if(pattern[idx] == pattern[len])
                    table[idx] = ++len;
            }
        }

        // KMP 알고리즘
        static boolean KMP() {
            int len=0;
            for(int idx=0; idx<origin.length; idx++) {
                if(len>0 && origin[idx] != pattern[len])
                    len = table[len-1];

                if(origin[idx] == pattern[len]) {
                    if(len == pattern.length-1)
                        return true;
                    else
                        len++;
                }
            }

            return false;
        }

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

            table = new int[pattern.length];
            makeTable();

            System.out.println(KMP() ? 1 : 0);
        }
    }

            
              📕 개인 기록용 블로그입니다.
              😊 오타나 잘못된 정보가 있을 경우 댓글이나 메일로 말씀해주시면 바로 수정하겠습니다! 😊