돌림판 문자열

시간 제한1초메모리 제한1024 MB

요약

알파벳이 적힌 돌림판과 목표 문자열 S가 주어질 때, S를 만들기 위한 최소 회전 수를 구하고 불가능하면 -1을 출력합니다.

문제

위 그림과 같이 알파벳 소문자가 한 글자씩 적힌 돌림판이 존재한다. 돌림판은 반시계 방향으로만 회전하며, 한번 회전할 때마다 시계방향으로 다음 문자를 가리킨다.

위와 같은 형태의 돌림판이 주어질 때 돌림판 문자열을 만들 수 있다. 돌림판 문자열은 처음에는 빈 문자열이며, 아래와 같은 작업을 유한 번 수행하여 만들 수 있는 문자열을 의미한다.

돌림판을 1회 회전시킨다.
아무것도 하지 않거나 문자열의 맨 끝에 돌림판이 가리키는 문자를 하나 추가한다. 돌림판 문자열이 빈 문자열일 때 돌림판이 가리키는 문자를 추가하는 경우 그 문자가 돌림판 문자열이 된다.

여러분이 할 일은 돌림판에 적힌 알파벳 소문자들이 시계 방향 순서대로 주어질 때 돌림판 문자열을 주어진 문자열 S로 만들 수 있는지, 만약 가능하다면 돌림판 문자열을 문자열 S로 만드는데 필요한 돌림판의 최소 회전 수를 구하는 것이다.

첫 번째 줄에 돌림판에 적힌 알파벳 소문자의 개수 N이 주어진다.

두 번째 줄에 돌림판에 적힌 알파벳 소문자 N개가 공백 없이 시계 방향 순서대로 주어진다. 돌림판은 처음에 마지막으로 입력된 문자를 가리키고 있다.

세 번째 줄에 만들어야 하는 문자열 S의 길이 M이 주어진다.

네 번째 줄에 길이가 M인 문자열 S가 주어진다.

돌림판 문자열을 문자열 S로 만들기 위해 필요한 돌림판 회전 수의 최솟값을 출력한다. 돌림판 문자열을 문자열 S로 만들 수 없다면 -1을 출력한다.