시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB217786134.270%

문제

"Jeremy Clarkson Beatbox" is a popular YouTube video montage of the former Top Gear host performing beatbox. The video consists of a series of scenes from the show, stitched together to produce an entertaining musical performance. The video was published on YouTube in 2009 and it has been viewed almost three million times since then.

This year Jeremy Clarkson departed from the BBC, following a disciplinary ruling. To commemorate the iconic show, we want to produce a sequel to the popular YouTube montage, using scenes from more recent episodes. The lyrics of the new video are already chosen by the fans of the show, but making the montage is not an easy thing.

The problem is that, no matter how skillfully the separate pieces of the video are stitched together, the transitions are always noticeable to the viewers. If two transitions occur within a short period of time, it can even be irritating for some viewers. Therefore, the goal is to keep the transitions as far apart as possible by maximizing the length of the shortest piece in the montage.

Write a program that takes two lines of input: the lyrics of the song on the first line, and the script of an episode of Top Gear on the second line. The program should then find the best way to construct the lyrics out of substrings of the script by maximizing the length of the shortest substring. It should output the length of the shortest substring in that optimal variant of the song. If it’s impossible to construct the song out of the given episode, it should output −1. 

입력

Your program should read from the standard input two lines of text, containing only English uppercase and lowercase letters.

출력

Your program has to write to the standard output one integer, which is equal to the length of the shortest substring in the optimal variant of the song, or -1 if construction is impossible.

제한

Each line in the input will be at most 100000 characters long.

Let us denote the length of the first string by N, and the length of the second string by M.

서브태스크

번호배점제한
111

N, M ≤ 10

217

N, M ≤ 2 000

319

N, M ≤ 10 000

423

N, M ≤ 30 000, The answer to the problem is less or equal to 20.

530

N, M ≤ 100 000.

예제 입력 1

JusticeAndTrust
CarsAndTrucksAreJustNice

예제 출력 1

3

힌트

Just|ice|AndTr|ust
Min(4, 3, 5, 3) = 3
CarsAndTrucksAreJustNice

채점 및 기타 정보

  • 예제는 채점하지 않는다.