Editorial for Appleby Contest '20 P3 - Ridiculous String

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

The answer is always $|T|$ ~|T|~.

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

If an answer exists, the prefix of the subsequence of $S$ ~S~ equal to $T$ ~T~ must contain at least one character from each copy of $s$ ~s~. Thus, we can just copy $s$ ~s~ $|T|$ ~|T|~ times and check that instead.

Time Complexity: $\mathcal{O}(|s||T|)$ ~\mathcal{O}(|s||T|)~

Memory Complexity: $\mathcal{O}(|s||T|)$ ~\mathcal{O}(|s||T|)~

Subtask 3

The solution is the same as the previous subtask except you don't explicitly copy $s$ ~s~.

Time Complexity: $\mathcal{O}(|s||T|)$ ~\mathcal{O}(|s||T|)~

Memory Complexity: $\mathcal{O}(|s|+|T|)$ ~\mathcal{O}(|s|+|T|)~

Subtask 4

Construct an array $nxt$ ~nxt~ where $nxt[i][j]$ ~nxt[i][j]~ contains the first index of the letter $j$ ~j~ in $s$ ~s~ with an index $>i$ ~>i~. This array can be used to find the smallest prefix in $\mathcal{O}(|T|)$ ~\mathcal{O}(|T|)~ time.

Time Complexity: $\mathcal{O}(|s|+|T|)$ ~\mathcal{O}(|s|+|T|)~

Comments

There are no comments at the moment.