34507번 - Scary Subsequences 다국어

In this problem, all strings consist only of four characters: a, b, c, and d.

Busy Beaver has three strings $x$, $y$, and $z$ that he's really scared of. In particular, he only likes strings that are not a subsequence of any of them.

Answer $Q$ queries. In query $i$, you are given a string $s_i$, such that $x$, $y$, and $z$ are all subsequences of $s_i$ and $|s_i| > \max(|x|, |y|, |z|)$. Help Busy Beaver find the length of the shortest subsequence of $s_i$ that is not a subsequence of any of $x$, $y$, or $z$.

¹A string $s$ is a subsequence of a string $t$ if $s$ can be obtained from $t$ by deleting some (possibly none or all) characters from $t$, without reordering the remaining characters.

The first three lines of the input contain the strings $x$, $y$, and $z$ ($1 \le |x|, |y|, |z| \le 60$), consisting of characters a, b, c, d.

The next line contains a single positive integer $Q$ ($1 \le Q \le 1.5 \cdot 10^5$).

The next $Q$ lines each contain a string, the $i$-th of which is $s_i$ ($\max(|x|, |y|, |z|) < |s_i| \leq 3 \cdot 10^5$), consisting of characters a, b, c, d such that $s_i$ has $x$, $y$, and $z$ as subsequences.

The sum of $|s_i|$ over all queries does not exceed $3 \cdot 10^5$.

On the $i$-th line, output a single positive integer --- the shortest possible length of a subsequence of $s_i$ that is not a subsequence of any of $x$, $y$, or $z$.

In the first query, all length $1$ subsequences of abcbc are subsequences of one of $x$, $y$, or $z$, but the subsequence cb is not, so the answer is $2$.

In the second query, d is a subsequence of dabcabc that is not a subsequence of any of $x$, $y$, or $z$.

In the third query, bbc is a subsequence of abbcc that is not a subsequence of any of $x$, $y$, or $z$, and it is the shortest such subsequence.