#255 Infinite String

Loading problem...

Preparing the statement, recent submissions, and submit form.

#255 Infinite String | DOJ

Authors: rladbeka

Statement

알파벳 소문자로만 이루어진 두 문자열 $S$ , $T$ 가 주어진다.

문자열 $T$ 를 무한히 이어 붙여 만든 무한 문자열 $TTTT\dots$ 에 대해, $S$ 와 $TTTT\dots$ 의 LCS (Longest Common Subsequence) 의 길이를 구하여라.

LCS란, 두 문자열의 최장 공통 부분수열을 의미한다.

입력은 다음과 같은 형식으로 주어진다.

$S$ $T$

첫째 줄에 $S$ 와 $TTTT\dots$ 의 최장 공통 부분수열의 길이를 출력한다.

Sample 1

Input

abac
ca

Output

$S$ 와 $TTTT\dots$ 의 LCS는 $\text{AAC}$ 이다.

Sample 2

Input

abcde
xyz

Output

Sample 3

Input

zzzz
az

Output