삽입

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

요약

문자열 s의 한 위치에 t를 끼워 넣어 p의 출현 횟수를 최대로 만듭니다. 최댓값, 그 값을 얻는 위치의 개수, 가장 작은 위치와 가장 큰 위치를 구합니다.

난이도: 보통10점 중 6점
유형: 문자열 매칭, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

세 문자열 $s$ , $t$ , $p$ 가 주어진다. 문자열의 길이는 세로 막대로 나타내며, $|s|$ 는 $s$ 의 길이이다. $0 \le k \le |s|$ 인 위치 $k$ 에 $t$ 를 삽입하면, $s$ 의 앞 $k$ 개 문자, 그다음 $t$ 전체, 마지막으로 $s$ 의 나머지 $|s| - k$ 개 문자로 이루어진 새 문자열이 된다. 결과 문자열에 $p$ 가 부분 문자열로 가장 많이 나타나도록 $k$ 를 고른다.

예를 들어 $s$ 가 ab이고 $t$ 가 aba일 때, $k = 0$ 이면 abaab, $k = 1$ 이면 aabab, $k = 2$ 이면 ababa가 된다. $p$ 가 aba라면 가장 좋은 위치는 $k = 2$ 이며, 등장 횟수는 두 번이다(ababa와 ababa). 등장 위치가 겹쳐도 센다. $p$ 가 aa라면 $k = 0$ 과 $k = 1$ 이 최선이고, 두 경우 모두 한 번씩 나타난다. $k = 2$ 에서는 한 번도 나타나지 않는다.

입력

첫째 줄에 문자열 $s$ , 둘째 줄에 $t$ , 셋째 줄에 $p$ 가 주어진다.

출력

다음 네 정수를 공백으로 구분하여 한 줄에 출력한다.

$t$ 를 $s$ 에 적절한 위치 $k$ 로 삽입했을 때 $p$ 가 나타나는 최대 횟수.
최대 횟수가 나타나는 $k$ 의 서로 다른 개수. $k$ 는 $0, 1, \ldots, |s|$ 중에서 고른다.
최대 횟수가 나타나는 $k$ 의 최솟값.
최대 횟수가 나타나는 $k$ 의 최댓값.

제한

$1 \leq |s| \leq 10^5$
$1 \leq |t| \leq 10^5$
$1 \leq |p| \leq 10^5$
모든 문자열은 영어 소문자로만 이루어진다.

예제3

예제 1
입력
```
ab
aba
aba
```
예상 출력
```
2 1 2 2
```
예제 2
입력
```
abaab
aba
ababa
```
예상 출력
```
1 3 1 5
```
예제 3
입력
```
eeoeo
eoe
eeo
```
예상 출력
```
2 3 1 4
```