Editorial for DMOPC '20 Contest 5 P1 - Home Row - Olympiads Online Judge

Editorial for DMOPC '20 Contest 5 P1 - Home Row

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: 4fecta

Note that it is both necessary and sufficient to change all characters that are not part of the longest common prefix of $S$ $S$ and $T$ $T$ . Thus, our answer is simply $|S| + |T| - 2 \times |LCP(S, T)|$ $| S | + | T | - 2 \times | L C P (S, T) |$ . A simple loop from the front of both strings is enough to compute the length of the longest common prefix in $\mathcal{O}(\min(|S|, |T|))$ $O (min (| S |, | T |))$ , and that is sufficient to solve the problem.

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

Comments

There are no comments at the moment.