[BOJ] 1786:찾기

0. 문제

https://www.acmicpc.net/problem/1728

1786번: 찾기

 

1. 문제분석

- 자료구조 시간에 배운 KMP 알고리즘을 사용해야 하는 전형적인 문제이다.

 

2. 주의할 점

- 자료구조 책을 펼치고 KMP 알고리즘을 다시 공부하자.

- 블로그에 설명이 참 잘되어 있다. bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

- KMP 알고리즘 내용 요약

1. 특정 문자열(P)와 그 속에서 특정 문자열을 찾아야 하는 긴 문자열(T)이 있다. 간단하게 생각해서 P와 T의 문자를 비교하고, T의 문자 인덱스를 하나씩 늘려가면서 T와 P를 비교하면 시간이 너무 오래 걸린다.

2. 문자열을 보다 빠르게 비교하기 위해서 prefix와 suffix 개념을 가져온다. 여기서 prefix는 어떤 문자열의 부분 문자열 중에서, 가장 첫번째 문자를 반드시 포함하는 부분 문자열이고, suffix는 가장 마지막 문자를 반드시 포함하는 문자열이다.

3. 특정 문자열 P에 대하여, 인덱스 i까지의 부분 문자열 중 prefix와 suffix가 동일함을 만족하면서 길이가 가장 긴 부분 문자열의 길이를 저장하는 failure[i] 값을 미리 찾아둔다.

4. failure 함수를 사용하여 T와 P를 비교할 때 일치하지 않는 문자가 나온다면 기존의 suffix 위치에 prefix를 위치시킨 후 문자열 비교를 실행한다. 즉, 문자열을 비교할 필요가 없는 경우는 건너뛰면서 문자열을 찾는다.

 

 

3. 소스코드(Java)

// boj 1786 : 찾기
// KMP 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class boj_01786 {

    static String T;
    static String P;
    static int[] failure;
    static LinkedList<Integer> ans = new LinkedList<>();

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

        // failure function :  문자열 P의 부분 문자열 중, prefix와 suffix가 동일한 최장길이를 미리 구해놓은 것
        // failure[i] : 문자열 P의 0부터 i까지의 부분 문자열(P[0..i]) 중, prefix와 suffix가 동일한 최장 길이
        // prefix는 무조건 0번째 문자부터 시작, suffix는 무조건 맨 마지막 문자로 끝남.
        // P의 길이가 l이고, failure[i] = f라면, P[0 .. f-1] == P[l-1-f .. l-1] (단, f<=i)
        int Plen = P.length(), j = 0;
        char[] Pchar = P.toCharArray();
        failure = new int [Plen];
        for (int i = 1; i < Plen; ++i) {
            // i는 suffix의 맨 마지막 문자, j는 prefix의 맨 마지막 문자이므로
            // 가장 긴 prefix부터 길이를 줄여나가면서 prefix==suffix를 만족하는 prefix 찾기.
            while (j > 0 && Pchar[i] != Pchar[j]) j = failure[j - 1];

            // 기존의 최장 prefix에 문자 하나(P[j]==P[i]) 더 해주기
            if (Pchar[i] == Pchar[j]) failure[i] = ++j;
        }

        // KMP 함수
        char[] Tchar = T.toCharArray();
        j = 0;
        for (int i = 0; i < T.length(); ++i) {
            while (j > 0 && Tchar[i] != Pchar[j]) j = failure[j - 1];
            if (Tchar[i] == Pchar[j]) {
                // P와 일치하는 T의 부분문자열 찾음
                // i - Plen + 1 : P와 일치하는 T의 부분 문자열이 시작되는 인덱스
                if (j == Plen - 1) {
                    ans.add(i - Plen + 1);
                    // 부분 문자열을 찾았으므로 prefix가 가장 긴 조건부터 while에서 찾을 수 있도록 리셋
                    j = failure[j];
                }
                else j++;
            }
        }

        System.out.println(ans.size());
        for (int a : ans) System.out.print((a+1) + " ");
    }
}

4. 여담

- KMP 알고리즘.. 추억이 새록새록...