25433번 - PLCS 서브태스크

PLCS(Prime Longest Common Subsequence, 소수 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 길이가 소수이면서 가장 긴 것을 찾는 문제이다.

문자열 $A$, $B$와 PLCS에 포함되어야 하는 문자 $X$와 PLCS에 포함되면 안되는 문자 $Y$가 주어진다. 문자 $X$를 포함하고 문자 $Y$를 포함하지 않는 문자열 $A$, $B$의 공통 부분 수열 중 길이가 소수이면서 가장 긴 문자열의 길이를 출력하자. 이러한 문자열이 존재하지 않으면 -1을 출력한다.

문자열 $A$, $B$와 문자 $X$, $Y$는 알파벳 소문자로 구성되어 있으며, 문자열 $A$, $B$에는 문자 $X$가 정확히 하나씩 존재한다.

첫째 줄에 문자열 $A$가 주어진다.

둘째 줄에 문자열 $B$가 주어진다. $(1 ≤ |A|$, $|B| ≤ 50,000)$

셋째 줄에 문자 $X$가 주어진다.

넷째 줄에 문자 $Y$가 주어진다. $(X \neq Y)$

첫째 줄에 문자 $X$를 포함하고 문자 $Y$를 포함하지 않는 문자열 $A$, $B$의 PLCS의 길이를 출력한다. 이러한 PLCS가 존재하지 않으면 -1을 출력한다.