F. We love Gromah!!!!!

发布时间: 2019年11月18日 17:29   最后更新: 2019年11月18日 17:31   时间限制: 1000ms   内存限制: 1024M

小喵喵要去经过迷途竹林拜访辉夜姬(Houraisan Kaguya)。现在小喵喵被困在迷途竹林里面了,他需要找到正确的竹子才能找到永远亭。在迷途竹林里面,所有的竹子排成一行,编号从左至右依次为 $1,\ 2,\ 3,\ ...,\ |T|$,每个竹子 $i$ 上面有一个英文字母 $c_i$,可以按照顺序把竹子上面的字母排成一个字符串 $T$。同时辉夜姬给了小喵喵一个字符串 $S$ 作为密码。对于每个竹子 $i$ 对应字母开始的后缀字符串 $T_i$(即由 $c_ic_{i+1}...c_{|T|}$ 构成的字符串),可以定义一个正确度 $C_i$。正确度为如果以 $S$ 在 $T_i$ 上进行匹配,能匹配上的字符总数。特别的,这里的匹配是可以循环进行的,即如果完整地匹配了一次 $S$,那么可以从 $T_i$ 当前最后匹配到的字符的位置的下一个位置开始,继续重新匹配 $S$,最终直到失配或者 $T_i$ 结束为止。那么正确的竹子就是正确度 $C_i$ 最大的那个竹子 $i$。如果有多个竹子的正确度同时最大,那么正确的竹子是编号最小(最靠左)的那个。所以小喵喵要怎么找到永远亭呢?

第一行输入一个字符串 $T$,表示从左到右的竹子上的字母连起来组成的字符串。

第二行输入一个字符串 $S$,表示作为密码的字符串。

输出正确的竹子的编号。(最左边的竹子编号为 $1$,之后依次为 $2,\ 3,\ ...,\ |T|$)。

复制
aabaaa
a
4
复制
abcde
f
1
复制
aabaaa
aba
2

$1 \leq |T|,\ |S| \leq 10^5$。

样例解释

样例 1:从第四个竹子开始能匹配 $3$ 次,这是最大的正确度。

样例 2:所有的正确度都是 $0$,故取最左边的点。

样例 3:从第 $2$ 个字符开始,可以匹配一轮 “aba”。然后进行第二轮匹配,从第 $5$ 个字符开始,再可以有 $1$ 次匹配,即 $T$ 的第 $5$ 个字符和 $S$ 的第 $1$ 个字符成功匹配。之后就无法继续匹配。所以匹配字符数为 $4$,匹配起点为 $2$。

2019 fdupc

2019 FDUPC 程序设计校赛网络赛