CLARKSON

"Jeremy Clarkson Beatbox"는 전 Top Gear 진행자가 비트박스를 하는 것처럼 보이는 유튜브 편집 영상이다. 방송의 여러 장면을 잘라 이어 붙여 하나의 연주로 만들었고, 2009년에 올라온 뒤 조회수가 300만 회에 가깝다.

올해 Jeremy Clarkson은 징계를 받고 BBC를 떠났다. 이 방송을 기념하려고 최근 회차의 장면으로 후속 편집 영상을 만들려고 한다. 노래 가사는 팬들이 이미 정해 두었지만, 편집 작업이 만만치 않다.

장면을 아무리 솜씨 좋게 이어 붙여도 전환 지점은 시청자 눈에 띈다. 전환이 짧은 간격으로 연달아 일어나면 거슬리기까지 한다. 그래서 전환 사이를 최대한 벌려야 하는데, 이는 편집에 쓴 가장 짧은 조각을 최대한 길게 만드는 것과 같다.

노래 가사와 한 회차의 대본이 주어진다. 가사를 앞에서부터 연속된 여러 조각으로 자르고 각 조각이 모두 대본에 연속으로 등장하도록 만들 때, 가장 짧은 조각의 길이를 최대로 하는 방법을 찾고 그때 가장 짧은 조각의 길이를 출력하는 프로그램을 작성하시오. 주어진 대본으로 가사를 만들 수 없으면 -1을 출력한다.

첫째 줄에 노래 가사가, 둘째 줄에 한 회차의 대본이 주어진다. 두 줄 모두 영어 대문자와 소문자로만 이루어진다.

첫째 줄에 최적으로 나누었을 때 가장 짧은 조각의 길이를 출력한다. 가사를 대본의 조각으로 만들 수 없으면 -1을 출력한다.

가사의 길이를 $N$, 대본의 길이를 $M$이라고 하자. $1 \le N \le 100000$이고 $1 \le M \le 100000$이다. 대문자와 소문자는 서로 다른 문자로 취급한다.

가사가 JusticeAndTrust이고 대본이 CarsAndTrucksAreJustNice이면 가사를 Just, ice, AndTr, ust 네 조각으로 자를 수 있다. 네 조각 모두 대본에 연속으로 등장하고, 길이는 차례대로 4, 3, 5, 3이며 최솟값은 3이다.