시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 2 | 2 | 2 | 100.000% |
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: aba
ba
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:
ab aba aba
2 1 2 2
abaab aba ababa
1 3 1 5
eeoeo eoe eeo
2 3 1 4
The first of these three examples is the one discussed earlier in the problem statement.
ICPC > Regionals > Europe > Central European Regional Contest > CERC 2022 H번