Appleby Contest '20 P3 - Ridiculous String

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

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 ss and TT, consisting of lowercase English letters. He defines the string SS as s+s+s+\dotss+s+s+\dots (infinite) and wants to know the shortest prefix of SS that contains TT as a subsequence. A string TT is a subsequence of a string SS if TT can be obtained from deleting some characters of SS without changing the order of the remaining characters.

Constraints

For all subtasks:

1 \le |s|, |T| \le 5 \times 10^51 \le |s|, |T| \le 5 \times 10^5

Strings ss and TT will consist only of lowercase characters.

Note: for any string xx, |x||x| is defined as its length.

Subtask 1 [5%]

1 \le |s|, |T| \le 5001 \le |s|, |T| \le 500

Strings ss and TT will consist only of the letter a.

Subtask 2 [10%]

1 \le |s|, |T| \le 5001 \le |s|, |T| \le 500

Subtask 3 [25%]

1 \le |s|, |T| \le 10\,0001 \le |s|, |T| \le 10\,000

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line will contain the integers |s||s| and |T||T|.

The second line will contain ss.

The third line will contain TT.

Output Specification

Output the length of the shortest prefix of SS that contains TT 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 1111 prefix of SS is aabbccaabbc. If we delete the 2^\text{nd}2^\text{nd}, 4^\text{th}4^\text{th}, 6^\text{th}6^\text{th}, 8^\text{th}8^\text{th}, and 10^\text{th}10^\text{th} characters of that prefix, we end up with abcabc, demonstrating that TT is a subsequence of that prefix. Additionally, it can be proven that no shorter prefix of SS exists that contains TT as a subsequence.

Sample Input 2

6 1
abcdef
z

Sample Output 2

-1

Sample Explanation 2

No prefix of SS exists that contains TT as a subsequence.


Comments

There are no comments at the moment.