Erase Subsequences
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dp, strings

You are given a string $$$s$$$. You can build new string $$$p$$$ from $$$s$$$ using the following operation no more than two times:

1. choose any subsequence $$$s_{i_1}, s_{i_2}, \dots, s_{i_k}$$$ where $$$1 \le i_1 < i_2 < \dots < i_k \le |s|$$$;
2. erase the chosen subsequence from $$$s$$$ ($$$s$$$ can become empty);
3. concatenate chosen subsequence to the right of the string $$$p$$$ (in other words, $$$p = p + s_{i_1}s_{i_2}\dots s_{i_k}$$$).

Of course, initially the string $$$p$$$ is empty.

For example, let $$$s = \text{ababcd}$$$. At first, let's choose subsequence $$$s_1 s_4 s_5 = \text{abc}$$$ — we will get $$$s = \text{bad}$$$ and $$$p = \text{abc}$$$. At second, let's choose $$$s_1 s_2 = \text{ba}$$$ — we will get $$$s = \text{d}$$$ and $$$p = \text{abcba}$$$. So we can build $$$\text{abcba}$$$ from $$$\text{ababcd}$$$.

Can you build a given string $$$t$$$ using the algorithm above?

Input format:
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

Next $$$2T$$$ lines contain test cases — two per test case. The first line contains string $$$s$$$ consisting of lowercase Latin letters ($$$1 \le |s| \le 400$$$) — the initial string.

The second line contains string $$$t$$$ consisting of lowercase Latin letters ($$$1 \le |t| \le |s|$$$) — the string you'd like to build.

It's guaranteed that the total length of strings $$$s$$$ doesn't exceed $$$400$$$.

Output format:
Print $$$T$$$ answers — one per test case. Print YES (case insensitive) if it's possible to build $$$t$$$ and NO (case insensitive) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
ababcd
abcba
a
b
defi
fed
xyz
x

Example output:
YES
NO
NO
YES

Editorial:
Let's look at string $$$t$$$. Since we should get it using no more than two subsequences, then $$$t = a + b$$$ where $$$a$$$ is the first subsequence and $$$b$$$ is the second one. In the general case, $$$a$$$ can be empty. Let iterate all possible lengths of $$$a$$$ ($$$0 \le |a| < |s|$$$), so we can check the existence of solution for each pair $$$a$$$ and $$$b$$$.
If we'd fix $$$a$$$ and $$$b$$$ we need to check the following: is it true that $$$s$$$ contains $$$a$$$ and $$$b$$$ as subsequences and these subsequences don't intersect. Initially, we can invent the following dp: let $$$dp[len_s][len_a][len_b]$$$ be $$$1$$$ if the prefix of $$$s$$$ of length $$$len_s$$$ contains prefixes of $$$a$$$ and $$$b$$$ of length $$$len_a$$$ and $$$len_b$$$ as non-intersecting subsequences. The transitions are straingforward: if $$$dp[len_s][len_a][len_b] = 1$$$ we can either skip $$$s[len_s]$$$ ($$$0$$$-indexed) and update $$$dp[len_s + 1][len_a][len_b]$$$. If $$$s[len_s] = a[len_a]$$$ ($$$0$$$-indexed) then we can update $$$dp[len_s + 1][len_a + 1][len_b]$$$ and if $$$s[len_s] = b[len_b]$$$ then we can update $$$dp[len_s + 1][len_a][len_b + 1]$$$. But this dp has complexity $$$O(|s|^3)$$$ in general case.
But we can transform it in the next way: instead of the boolean value, we will make $$$len_s$$$ as a value of dp. In other words, we will maintain $$$dp[len_a][len_b]$$$ as minimal appropriate prefix $$$len_s$$$. But the problem now is to define transitions.
Let's note the next fact: suppose we have $$$len_s = dp[len_a][len_b]$$$ and we'd like to add next character to $$$a$$$ which is equal to $$$a[len_a]$$$. The idea is next: it's always optimal to choose the first occurrence of $$$a[len_a]$$$ in $$$s[len_s \dots |s|)$$$. It can be proved by contradiction: if the first occurrence is free then it's better to take it, or if the first occurrence will be occupied by $$$b$$$ then this will be handled by the other state $$$dp[len_a][len_b']$$$ with $$$len_b' > len_b$$$.
The logic for increasing $$$len_b$$$ is analogical. In result, we need to precalculate array $$$nxt[pos][c]$$$ with the next occurrence of character $$$c$$$ in suffix $$$pos$$$ of $$$s$$$ one time before choosing $$$a$$$ and $$$b$$$ and use it each time to acquire $$$O(|s|^2)$$$ complexity.
The total complexity if $$$O(|s|^3)$$$ for each test case.