[백준]#9253 스페셜 저지

12580 단어 algorithm백준KMPKMP

문제

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;
    }
}

좋은 웹페이지 즐겨찾기