Problem Description

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.

Input Format

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

The second line contains a string $D$, representing the given gene.

Output Format

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.

TCG
ATCACAGGT

7

Hint

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