Because chu problem de ren 给了九个 Subtask,我也不知道怎么回事,后面的 Subtask 可能会配错,ごめんなさい!
Description
Insert string $T$ into $S$ to maximize the number of occurrence of patterns $P$.
Input
Read the testdata from lgs.in
.
The first line contains the string $S$, the second line the string $T$, and the third line the string $P$.
Ouput
Print the answer to lgs.out
.
Output one line containing the following four integers, separated by spaces:
- 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.
- The number of different $k$’s (from the range $0, 1, \cdots , |S|$) where this maximum number of occurrences of $P$ is attained.
- The minimum value of $k$ where the maximum number of occurrences of $P$ is attained.
- The maximum value of $k$ where the maximum number of occurrences of $P$ is attained.
Range
保证 $1 \le |S|, |T|, |P| \le 10^5$,所有字符串只包含小写英文字母。
- 子任务 $1$($5$ 分):$|S|, |T|, |P| \le 10$。
- 子任务 $2$($15$ 分):$|S|, |T|, |P| \le 5000$。
- 子任务 $3$($20$ 分):$|T| \ge |P|$。
- 子任务 $4$($50$ 分):$|T| \le |P|$。
- 子任务 $5$($10$ 分):无特殊限制。