Statement
알파벳 소문자로만 이루어진 두 문자열 , 가 주어진다.
문자열 를 무한히 이어 붙여 만든 무한 문자열 에 대해, 와 의 LCS (Longest Common Subsequence) 의 길이를 구하여라.
LCS란, 두 문자열의 최장 공통 부분수열을 의미한다.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
첫째 줄에 와 의 최장 공통 부분수열의 길이를 출력한다.
Constraints
- .
- .
- 와 는 알파벳 소문자로만 이루어져 있다.
Subtasks
Samples
Sample 1
Input
abac
ca
Output
3
와 의 LCS는 이다.
Sample 2
Input
abcde
xyz
Output
0
Sample 3
Input
zzzz
az
Output
4