구간 성분

매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로부터 발생한 신호를 서열로 표시한 \(S_{A}\), \(S_{B}\)의 예는 다음과 같다.

• \(S_{A}\) = [a, f, c, d, r, d, e, s, d, c, f, w, s, z, r]

• \(S_{B}\) = [g, e, d, s, r, d, d, e, m, z, r]

신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의 성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 \(S_{A}\), \(S_{B}\)에서 성분이 같은 구간을 나타내고 있다.

즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분 의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에 서 가장 긴 것을 찾으려고 한다.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 \(1 \le N,\) \(M \le 1{,}500\) 이다.

두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2015 > 2차 대회 > 고등부 2번