[백준]#16172 나는 친구가 적다(Large)

문제

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

입력

첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 200,000)

단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.

출력

첫 번째 줄에 성민이가 찾고자 하는 키워드가 교과서 내에 존재하면 1, 존재하지 않으면 0을 출력한다.

예제 입력 1

1q2w3e4r5t6y
qwerty

예제 출력 1

1

예제 입력 2

1ovey0uS2
veS

예제 출력 2

0

풀이

이 문제는 KMP 알고리즘을 이용해서 풀 수 있었다. KMP 알고리즘이 조금 어려워서 여러번 보면서 이해하고 문제에 적용해보려고 연습중이다.

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().replaceAll("[0-9]", "");       //문자열에서 숫자 
        String pattern = br.readLine();

        int ans = kmp(str, pattern);

        System.out.println(ans);
    }

    public static int kmp(String str, String pattern) {
        int[] pi = getPi(pattern);
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int j = 0;

        for(int i=0; i<s.length; i++) {

            while(j>0 && s[i]!=p[j]) {
                j = pi[j-1];
            }

            if(s[i]==p[j]) {
                if(j==p.length-1)
                    return 1;
                else
                    j++;
            }
        }

        return 0;
    }

    public static int[] getPi(String pattern) {
        int[] pi = new int[pattern.length()];
        char[] p = pattern.toCharArray();
        int j = 0;

        for(int i=1; i<pattern.length(); i++) {
            while(j>0 && p[i]!=p[j]) {
                j = pi[j-1];
            }

            if(p[i]==p[j]) {
                pi[i] = ++j;
            }
        }

        return pi;
    }
}