26193번 - Insertions 다국어

문제

We are given three strings, $s,ドル $t$ and $p$. We will denote the length of a string by vertical bars, thus $|s|$ is the length of $s$ and so on. If we insert $t$ into $s$ at position $k,ドル where 0ドル \le k \le |s|,ドル the result is a new string consisting of the first $k$ characters of $s,ドル followed by the entirety of $t,ドル and finally followed by the remaining $|s| - k$ characters of $s$. We would like to select $k$ so that the resulting new string will contain the largest possible number of occurrences of $p$ as a substring.

Thus, for example, inserting $t = $aba into $s = $ab at position $k = 0$ results in the string abaab; at $k = 1,ドル in the string aabab; and at $k = 2,ドル in the string ababa. If we are interested in occurrences of $p = $aba, then the best position to insert $t$ into $s$ is $k = 2,ドル where we get two occurrences: ababa and ababa (as this example shows, occurrences of $p$ are allowed to overlap). If, on the other hand, we were interested in occurrences of $p = $aa, then the best choices of $k$ would be $k = 0$ and $k = 1,ドル which result in one occurrence of $p,ドル whereas $k = 2$ results in 0 occurrences of $p$.

입력

The first line contains the string $s,ドル the second line the string $t,ドル and the third line the string $p$.

출력

Output one line containing the following four integers, separated by spaces:

1. The maximum number of occurrences of $p$ we can get after inserting $t$ into $s$ at position $k,ドル if we choose the position $k$ wisely.
2. The number of different $k$'s (from the range 0,ドル 1, \ldots, |s|$) where this maximum number of occurrences of $p$ is attained.
3. The minimum value of $k$ where the maximum number of occurrences of $p$ is attained.
4. The maximum value of $k$ where the maximum number of occurrences of $p$ is attained.

제한

• 1ドル \leq |s| \leq 10^5$
• 1ドル \leq |t| \leq 10^5$
• 1ドル \leq |p| \leq 10^5$
• All the strings consist only of lowercase letters of the English alphabet.

노트

The first of these three examples is the one discussed earlier in the problem statement.