문제
매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로 부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다.
신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의성분’은 같다고 한다.
아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다.
즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분의 구간은 하나 이상 존재할 수 있다.
우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에서 가장 긴 것을 찾으려고 한다.
입력
표준 입력으로 다음의 정보가 주어진다.
첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다.
이 문자열은 영문 소문자로만 구성되어 있다.
두 입력 문자열의 크기 N,M 의 범위는 5≤N,M≤1,500이다.
출력
표준 출력으로 두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | N,M≤100 |
| #2 | 23점 | N,M≤500 |
| #3 | 31점 | N,M≤1,000 |
| #4 | 39점 | N,M≤1,500 |
예제1
입력
xraphy
edgeedgem
출력
0
예제2
입력
afcdrdesdefwszr
gedsrddemzr
출력
7
예제3
입력
computersystem
sesystuercomplexity
출력
11
출처
KOI 전국 2015 고2