[백준]#9253 스페셜 저지

문제

9249번 문제 (최장 공통 부분 문자열)의 채점 프로그램을 작성하시오.

문제의 조건은 동일하다. 편의상 사용자가 출력한 문자열의 길이가 문제의 답과 동일하고, 답은 0보다 크다고 가정한다.

입력

두 문자열 A 와 B 가 한 줄에 하나씩 주어진다. 두 문자열 길이의 합은 20만을 넘지 않는다.

세 번째 줄에 사용자가 출력한 문자열이 주어진다. 입력으로 주어지는 모든 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 20만을 넘지 않는다.

출력

답이 맞으면 YES, 틀리면 NO를 출력한다.

예제 입력 1

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother
howmuchiloveyoumydearmother

예제 출력 1

YES

풀이

이 문제는 KMP 알고리즘을 이용해서 풀 수 있는 문제였다. 이 문제 내부에 링크된 9249번 문제에 따르면 패턴이 '최장 길이가 맞는 지', '두 문자열에 모두 포함되는 지' 를 모두 확인해야 할 것 같은데 두 문자열에 존재하는 지 만으로 구현해도 풀 수 있었다.

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

public class Main {
    static String pattern;
    static int[] pi;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        pattern = br.readLine();
        getPi();

        if(kmp(str1) && kmp(str2))
            System.out.println("YES");

        else
            System.out.println("NO");
    }

    public static boolean kmp(String str) {
        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 true;
                }

                else
                    j++;
            }
        }

        return false;
    }

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

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

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

        return pi;
    }
}