[백준]#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;
}
}
Author And Source
이 문제에 관하여([백준]#9253 스페셜 저지), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준9253-스페셜-저지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)