Home

Problem Statement

Given are two strings $s$ and $t$ consisting of lowercase English letters. Determine if there exists an integer $i$ satisfying the following condition, and find the minimum such $i$ if it exists.

• Let $s'$ be the concatenation of $10^{100}$ copies of $s$. $t$ is a subsequence of the string ${s'}_1{s'}_2\ldots{s'}_i$ (the first $i$ characters in $s'$).

Notes

• A subsequence of a string $a$ is a string obtained by deleting zero or more characters from $a$ and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

• $1 \leq |s| \leq 10^5$
• $1 \leq |t| \leq 10^5$
• $s$ and $t$ consists of lowercase English letters.

Sample Input 1

contest
son

Sample Output 1

10

$t =$ son is a subsequence of the string contestcon (the first $10$ characters in $s' =$ contestcontestcontest...), so $i = 10$ satisfies the condition.

On the other hand, $t$ is not a subsequence of the string contestco (the first $9$ characters in $s'$), so $i = 9$ does not satisfy the condition.

Similarly, any integer less than $9$ does not satisfy the condition, either. Thus, the minimum integer $i$ satisfying the condition is $10$.

Sample Input 2

contest
programming

Sample Output 2

-1

$t =$ programming is not a substring of $s' =$ contestcontestcontest.... Thus, there is no integer $i$ satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a $32$-bit integer type, though we cannot put such a case here.