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 \le |A|, |B| \le 50,000)$

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

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

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