부분 문자열 뒤집기

면접 대비

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

요약

길이 2 이상인 부분 문자열 하나를 뒤집은 결과가 주어질 때, 뒤집힌 구간을 찾고 시작 위치가 가장 작은 답을 출력한다.

난이도: 보통10점 중 4점
유형: 문자열, 투 포인터
정답자: 아직 제출이 없습니다

문제

글렌은 여러 가지 문자열 변환을 연구하는 것을 좋아합니다. 요즘 그는 이른바 뒤집기(reversal) 변환에 관심이 있습니다. 뒤집기란, 문자열에서 두 개 이상의 문자로 이루어진 연속된 한 부분을 골라 그 부분만 거꾸로 쓰고 나머지 부분은 그대로 두는 변환입니다. 편의상 글렌은 대문자 라틴 알파벳으로만 이루어진 문자열만 다룹니다.

예로, 문자열 LABASRYTAS에 뒤집기 변환을 적용한 몇 가지 결과입니다 (뒤집힌 부분을 굵게 표시).

LABASRYTAS → LASABRYTAS
LABASRYTAS → SATYRSABAL
LABASRYTAS → ALBASRYTAS

글렌은 방금 서로 다른 두 문자열을 받았고, 두 번째 문자열이 첫 번째 문자열에 뒤집기 연산을 정확히 한 번 적용해 얻어진 것이라고 확신합니다. 하지만 어느 부분이 뒤집혔는지는 정확히 알아내지 못하고 있습니다.

뒤집힌 부분을 찾아 글렌을 도와줄 수 있나요?

입력

첫째 줄에 원본(그리고 변환된) 문자열의 길이 $N$ 이 주어집니다. 둘째 줄에는 원본 문자열이, 셋째 줄에는 변환된 문자열이 주어집니다.

두 문자열은 모두 대문자 라틴 알파벳으로만 이루어져 있습니다.

입력은 항상 답이 존재하도록 주어지며, 원본 문자열과 뒤집기 후의 문자열은 서로 다릅니다.

출력

뒤집힌 부분의 첫 번째 문자와 마지막 문자의 번호, 두 정수를 출력합니다. 문자의 번호는 왼쪽에서 오른쪽으로 $1$ 부터 $N$ 까지 매깁니다.

가능한 답이 여러 개라면 첫 번째 문자의 번호가 가장 작은 것을 출력합니다. 그래도 여전히 여러 개라면 그중 마지막 문자의 번호가 가장 작은 것을 출력합니다.

제한

$2 \le N \le 100000$

예제2

예제 1
입력
```
7
SAVASIS
SAVSAIS
```
예상 출력
```
4 5
```
예제 2
입력
```
10
LABASRYTAS
LASABRYTAS
```
예상 출력
```
3 5
```