P15854 [Lanqiao Cup 2nd International Contest] Gene Subsequence.

A biological gene is made up of $4$ different bases, usually denoted by A, T, G, and C. A gene can be represented as a sequence of bases in order, for example, ATCACAGGT. Xiaoming has recently been paying attention to a special base sequence $S$ (and $S$ is also composed of A, T, G, and C). He found that if, in a gene, we can extract some bases in their order of appearance and make them exactly equal to $S$, then the gene may have some property. For example, when $S=\text{TCG}$, we can extract the $2$nd, $3$rd, and $7$th bases from the gene ATCACAGGT to match $S$, but we cannot extract a part of the gene CGT to match $S$. Of course, the extraction positions can be varied. For instance, we can extract the $2$nd, $5$th, and $8$th bases from the gene ATCACAGGT to match $S$. Xiaoming wants to know: among all ways that can make them equal, what is the minimum possible index of the last extracted base in the gene.

The first line contains a string $S$, representing the given base sequence. The second line contains a string $D$, representing the given gene.

If no valid extraction method can be found, output $-1$. Otherwise, output the index of the last extracted base in the gene when they are equal.

### Sample Explanation This problem asks for the minimum answer. If you output $8$, it is incorrect. ### Constraints For $40\%$ of the test cases, the lengths of both strings do not exceed $1000$. For all test cases, the lengths of both strings do not exceed $100000$. The characters that appear are only A, T, C, and G. Translated by ChatGPT 5