Yesterday, Mrs. Truong gave Ridiculous Ray a task about strings as part of his ICS3U summative. However, as he did not find the task to be ridiculous enough for his taste, he has decided that you should solve it instead.
The task is as follows:
Ridiculous Ray was given the strings
and
, consisting of lowercase English letters. He defines the string
as
(infinite) and wants to know the shortest prefix of
that contains
as a subsequence. A string
is a subsequence of a string
if
can be obtained from deleting some characters of
without changing the order of the remaining characters.
Constraints
For all subtasks:
Strings and
will consist only of lowercase characters.
Note: for any string ,
is defined as its length.
Subtask 1 [5%]
Strings and
will consist only of the letter
a
.
Subtask 2 [10%]
Subtask 3 [25%]
Subtask 4 [60%]
No additional constraints.
Input Specification
The first line will contain the integers and
.
The second line will contain .
The third line will contain .
Output Specification
Output the length of the shortest prefix of that contains
as a subsequence, or
-1
if no such prefix exists.
Sample Input 1
6 6
aabbcc
abcabc
Sample Output 1
11
Sample Explanation 1
The length prefix of
is
aabbccaabbc
. If we delete the ,
,
,
, and
characters of that prefix, we end up with
abcabc
, demonstrating that is a subsequence of that prefix. Additionally, it can be proven that no shorter prefix of
exists that contains
as a subsequence.
Sample Input 2
6 1
abcdef
z
Sample Output 2
-1
Sample Explanation 2
No prefix of exists that contains
as a subsequence.
Comments