만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

돌림판 문자열

면접 대비

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

요약
회전하는 바퀴에 적힌 글자로 문자열 S를 만들 때 필요한 최소 회전 수를 구하고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 시뮬레이션
정답자
아직 제출이 없습니다

문제

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

이런 돌림판이 주어지면 돌림판 문자열을 만들 수 있다. 돌림판 문자열은 처음에는 빈 문자열이며, 아래 작업을 유한 번 수행하여 만들 수 있는 문자열을 뜻한다.

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

돌림판에 적힌 알파벳 소문자가 시계 방향 순서대로 주어질 때, 돌림판 문자열을 문자열 S로 만들 수 있는지 판단한다. 만들 수 있다면 S를 만드는 데 필요한 돌림판의 최소 회전 수를 구한다.

입력

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

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

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

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

출력

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

제한

1 ≤ N ≤ 100

1 ≤ M ≤ 100

S는 알파벳 소문자로만 이루어져 있다.

예제3

  1. 예제 1

    입력
    4
    abcd
    6
    aacdbc
    
    예상 출력
    11
    
  2. 예제 2

    입력
    9
    algorithm
    4
    gori
    
    예상 출력
    6
    
  3. 예제 3

    입력
    14
    inhauniversity
    5
    igrus
    
    예상 출력
    -1