시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 3 3 60.000%

문제

두 문자열 s와 t가 주어진다. s와 t의 모든 문자는 다르다. s에 등장하는 모든 문자는 t에 등장하지 않으며, t에 등장하는 모든 문자는 s에도 등장하지 않는다.

s의 길이를 N, t의 길이를 M이라고 한다. 또, 다음과 같이 정의되는 2차원 배열 table이 있다.

  • table[i][0] = s[i-1] (1 ≤ i ≤ N)
  • table[0][j] = t[j-1] (1 ≤ j ≤ M)
  • table[i][j] = min(table[i-1][j], table[i][j-1]) + max(table[i-1][j], table[i][j-1]) (1 ≤ i ≤ N, 1 ≤ j ≤ M)

min은 두 문자열 중 사전 순으로 앞서는 것을 리턴하는 함수이며, max는 두 문자열 중 사전 순으로 뒤에 있는 것을 리턴하는 함수이다. 또, A+B는 문자열A의 뒤에 B를 연결하는 연산이다.

table[N][M]의 부분 문자열을 구하는 프로그램을 작성하시오. 이 때, 부분 문자열의 길이가 너무 길어질 수 있기 때문에, pos번째부터 min(50, L-pos)개의 문자를 출력한다. 여기서 L은 table[N][M]의 길이이다.

입력

첫째 줄에 s, 둘째 줄에 t, 셋째 줄에 pos가 주어진다. (0 ≤ pos < L)

s와 t의 길이는 30보다 작거나 같은 자연수이며, 알파벳 대문자/소문자와 숫자로만 이루어져 있다.

출력

첫째 줄에 table[N][M]의 pos번째부터 min(50, L-pos)개수 만큼 부분 문자열을 출력한다.

예제 입력 1

ad
cb
0

예제 출력 1

acbacd

예제 입력 2

fox
cat
0

예제 출력 2

acfcfoacftacfcfocfox

예제 입력 3

Ra6b1t
W0lf
66

예제 출력 3

RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6

예제 입력 4

M0HAXG
COFU12
919

예제 출력 4

MOFU2

예제 입력 5

a0B1c2D3e4F5gHiJkLmN
A9b8C7d6EfGhIjKlMn
9876543210

예제 출력 5

B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9

출처