의사매듭

RNA 가닥을 대문자 문자열로 적는다. 가닥이 접히면 뒤집힌 두 쌍의 구간이 서로 엇갈리는 구조가 나타나고, 이 구조를 의사매듭이라고 한다. 연결이 길수록 구조가 안정적이므로, 새로운 가닥을 분석할 때는 연결이 가장 긴 의사매듭을 찾는다.

문자열 $w$를 이어지는 여섯 부분으로 잘라

$w = u\,v\,z^R\,u^R\,y\,z$

로 쓸 수 있으면 $w$는 의사매듭이다. $u^R$과 $z^R$은 각각 $u$와 $z$를 뒤집은 문자열이다. $|u| \ge 1$이고 $|z| \ge 1$이며, $v$와 $y$는 빈 문자열이어도 된다. 쌍 $(u, u^R)$이 하나의 연결이고 쌍 $(z, z^R)$이 다른 연결이다.

예를 들어 ICPCINAEROKCPCIFORKOREA는 $u$ = ICPC, $v$ = IN, $z^R$ = AEROK, $u^R$ = CPCI, $y$ = FOR, $z$ = KOREA로 잘리므로 의사매듭이다. AQQQQRRRRRQQQQQ는 어떻게 잘라도 이 형태가 나오지 않으므로 의사매듭이 아니다.

그림 1. 의사매듭인 문자열 (a)와 의사매듭이 아닌 문자열 (b)

ICPCAEROKCPCIKOREA는 $v$와 $y$가 모두 빈 문자열이지만 의사매듭이다. 비어 있으면 안 되는 부분은 $u$와 $z$뿐이다.

그림 2. $v$와 $y$가 빈 의사매듭

한 문자열이 여러 의사매듭 구조를 가지기도 한다. ICPCINAEROKCPCIAECIKOREA는 $u$ = ICPC, $v$ = IN, $z^R$ = AEROK, $u^R$ = CPCI, $y$ = AECI, $z$ = KOREA로 잘리고, $u$ = IC, $v$ = PCINAEROKCPCI, $z^R$ = AE, $u^R$ = CI, $y$ = KOR, $z$ = EA로도 잘린다. 앞쪽 구조의 연결이 더 기니 앞쪽 구조를 답으로 삼는다.

그림 3. 같은 문자열의 서로 다른 의사매듭 구조 두 가지

표준 입력으로 읽는다. 입력은 대문자로만 이루어진 문자열 하나이고, 중간에 공백이나 줄바꿈은 없다. 문자열의 길이는 1 이상 200,000 이하다.

표준 출력으로 쓴다. 입력 문자열 $w$를 $w = u\,v\,z^R\,u^R\,y\,z$로 자르면서 $|u| \ge t$, $|z| \ge t$, $|v| \ge 0$, $|y| \ge 0$을 만족시키는 가장 큰 정수 $t$를 한 줄에 출력한다. 그런 $t$가 없으면, 즉 $w$가 의사매듭이 아니면 -1을 출력한다.