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)$ $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|)$ $O (| s | | T |)$

Memory Complexity: $\mathcal{O}(|s||T|)$ $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|)$ $O (| s | | T |)$

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

Subtask 4

Construct an array $nxt$ $n x t$ where $nxt[i][j]$ $n x t [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|)$ $O (| T |)$ time.

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

Comments

There are no comments at the moment.