손상된 비밀번호
면접 대비시간 제한2초메모리 제한1024 MB
문자열 s와 t가 주어졌을 때, s의 위치 x를 다른 문자 c로 바꾸면 s가 t의 부분수열이 되도록 x와 c를 구합니다.
문제
Vi에게는 아주 중요한 비밀 문자열 가 있었다. 그는 이 문자열에 다음과 같은 연산을 순서대로 적용했다.
- 문자열 에서 위치 를 고르고, 를 문자 로 바꾼다 (, ).
- 문자열의 임의의 위치에 임의의 문자를 0번 이상 삽입한다. 문자는 첫 문자 앞, 인접한 두 문자 사이, 마지막 문자 뒤 어디에든 넣을 수 있다.
그 결과 문자열 가 만들어졌다. 문자열 와 가 주어질 때, Vi가 고른 위치 와 문자 를 찾아라.
입력
첫 번째 줄에 소문자 영문자로 이루어진 문자열 가 주어진다 ().
두 번째 줄에 소문자 영문자로 이루어진 문자열 가 주어진다 ().
는 위에서 설명한 과정을 거쳐 로부터 만들어졌다고 보장된다.
출력
Vi가 고를 수 있었던 위치 와 문자 를 출력한다. 반드시 여야 한다. 답이 여러 개라면 그중 아무거나 출력해도 된다.