410785: GYM104114 A AppendAppendAppend

Momo has a string $$$s$$$ which he plays with. After each day, he takes the initial string and appends it to the one that he currently has, that is, if the string is "$$$abc$$$", on the first day the string will remain "$$$abc$$$", on the second day the string will become "$$$abcabc$$$", on the third day the string becomes "$$$abcabcabc$$$", and so on.

Bobo has another string $$$t$$$. Bobo is curious whether his string $$$t$$$ can be found as a subsequence in Momo's string. He is curious what is the first day when this property will hold.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

The first line of the input contains Momo's string $$$s$$$.

The second line of the input contains Bobo's string $$$t$$$.

Both strings have lengths at least $$$1$$$ and at most $$$5\cdot 10^5$$$ and contain only lowercase letters of the English alphabet.

Output a single integer  — the number of the day when Bobo's string will be a subsequence of Momo's string for the first time.

It is guaranteed that for all test cases in this problem such a day exists.

dwalkcake
cakewalk

2

During the first day, the string is "$$$dwalkcake$$$", and doesn't contain "$$$cakewalk$$$" as a subsequence.

During the second day, the string is "$$$dwalkcakedwalkcake$$$", and it contains "$$$cakewalk$$$" as a subsequence.