만드는 중입니다

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

손상된 비밀번호

면접 대비

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

요약
문자열 s와 t가 주어졌을 때, s의 위치 x를 다른 문자 c로 바꾸면 s가 t의 부분수열이 되도록 x와 c를 구합니다.
난이도

보통10점 중 5점

유형
그리디, 문자열, 투 포인터
정답자
아직 제출이 없습니다

문제

Vi에게는 아주 중요한 비밀 문자열 ss가 있었다. 그는 이 문자열에 다음과 같은 연산을 순서대로 적용했다.

  1. 문자열 ss에서 위치 xx를 고르고, sxs_x를 문자 cc로 바꾼다 (1≤x≤∣s∣1 \le x \le |s|, sx≠cs_x \neq c).
  2. 문자열의 임의의 위치에 임의의 문자를 0번 이상 삽입한다. 문자는 첫 문자 앞, 인접한 두 문자 사이, 마지막 문자 뒤 어디에든 넣을 수 있다.

그 결과 문자열 tt가 만들어졌다. 문자열 ss와 tt가 주어질 때, Vi가 고른 위치 xx와 문자 cc를 찾아라.

입력

첫 번째 줄에 소문자 영문자로 이루어진 문자열 ss가 주어진다 (1≤∣s∣≤1061 \le |s| \le 10^6).

두 번째 줄에 소문자 영문자로 이루어진 문자열 tt가 주어진다 (∣s∣≤∣t∣≤106|s| \le |t| \le 10^6).

tt는 위에서 설명한 과정을 거쳐 ss로부터 만들어졌다고 보장된다.

출력

Vi가 고를 수 있었던 위치 xx와 문자 cc를 출력한다. 반드시 sx≠cs_x \neq c여야 한다. 답이 여러 개라면 그중 아무거나 출력해도 된다.

예제1

  1. 예제 1

    입력
    abc
    aacc
    
    예상 출력
    2 a