310517: CF1845C. Strong Password
Description
Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.
He wants his password to be as strong as possible, so he came up with the following criteria:
- the length of the password should be exactly $m$;
- the password should only consist of digits from $0$ to $9$;
- the password should not appear in the password database (given as a string $s$) as a subsequence (not necessarily contiguous).
Monocarp also came up with two strings of length $m$: $l$ and $r$, both consisting only of digits from $0$ to $9$. He wants the $i$-th digit of his password to be between $l_i$ and $r_i$, inclusive.
Does there exist a password that fits all criteria?
InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
The first line of each testcase contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting only of digits from $0$ to $9$ — the password database.
The second line contains a single integer $m$ ($1 \le m \le 10$) — the required length of the password.
The third line contains a string $l$ ($|l| = m$), consisting only of digits from $0$ to $9$ — the lower restriction on each digit.
The fourth line contains a string $r$ ($|r| = m$), consisting only of digits from $0$ to $9$ — the upper restriction on each digit. $l_i \le r_i$ for all $i$ from $1$ to $m$.
The sum of lengths of $s$ over all testcases doesn't exceed $3 \cdot 10^5$.
OutputFor each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise.
ExampleInput5 88005553535123456 2 50 56 123412341234 3 111 444 1234 4 4321 4321 459 2 49 59 00010 2 10 11Output
YES NO YES NO YESNote
In the first testcase, Monocarp can choose password "50". It doesn't appear in $s$ as a subsequence.
In the second testcase, all combinations of three digits, each of them being from $1$ to $4$, fit the criteria on $l$ and $r$. However, all of them appear in $s$ as subsequences. For example, "314" appears at positions $[3, 5, 12]$ and "222" appears at positions $[2, 6, 10]$.
In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $l$ and $r$. Luckily, it doesn't appear in $s$ as a subsequence.
In the fourth testcase, only "49" and "59" fit the criteria on $l$ and $r$. Both of them appear in $s$ as subsequences.
In the fifth testcase, Monocarp can choose password "11".
Input
题意翻译
给定一个字符串 $s$,以及两个长度为 $m$ 的字符串 $l,r$。你需要判断是否**没有**长度为 `m` 的字符串 $t$ 满足以下要求: 1. 对于 $1\le i\le n$,$l_i\le t_i\le r_i$。 2. $t$ **不是** $s$ 的一个子序列。Output
单字符 Monocarp 在注册 ForceCoders 时想要一个尽可能强的密码。他设定了以下标准:
- 密码长度必须是 m;
- 密码只能由 0 到 9 的数字组成;
- 密码不能出现在密码数据库(字符串 s)中作为一个子序列(不一定是连续的)。
Monocarp 还提出了两个长度为 m 的字符串 l 和 r,它们都只包含 0 到 9 的数字。他希望密码的第 i 位数字在 l_i 和 r_i 之间,包括 l_i 和 r_i。
输入输出数据格式:
输入:
- 第一行包含一个整数 t(1 ≤ t ≤ 10^4)——测试用例的数量。
- 每个测试用例的第一行包含一个字符串 s(1 ≤ |s| ≤ 3 * 10^5),由 0 到 9 的数字组成——密码数据库。
- 第二行包含一个整数 m(1 ≤ m ≤ 10)——所需密码的长度。
- 第三行包含一个字符串 l(|l| = m),由 0 到 9 的数字组成——每个数字的下限。
- 第四行包含一个字符串 r(|r| = m),由 0 到 9 的数字组成——每个数字的上限。对于所有 1 到 m 的 i,有 l_i ≤ r_i。
- 所有测试用例中 s 的长度之和不超过 3 * 10^5。
输出:
- 对于每个测试用例,如果存在符合所有条件的密码,则输出 "YES",否则输出 "NO"。题目大意: 单字符 Monocarp 在注册 ForceCoders 时想要一个尽可能强的密码。他设定了以下标准: - 密码长度必须是 m; - 密码只能由 0 到 9 的数字组成; - 密码不能出现在密码数据库(字符串 s)中作为一个子序列(不一定是连续的)。 Monocarp 还提出了两个长度为 m 的字符串 l 和 r,它们都只包含 0 到 9 的数字。他希望密码的第 i 位数字在 l_i 和 r_i 之间,包括 l_i 和 r_i。 输入输出数据格式: 输入: - 第一行包含一个整数 t(1 ≤ t ≤ 10^4)——测试用例的数量。 - 每个测试用例的第一行包含一个字符串 s(1 ≤ |s| ≤ 3 * 10^5),由 0 到 9 的数字组成——密码数据库。 - 第二行包含一个整数 m(1 ≤ m ≤ 10)——所需密码的长度。 - 第三行包含一个字符串 l(|l| = m),由 0 到 9 的数字组成——每个数字的下限。 - 第四行包含一个字符串 r(|r| = m),由 0 到 9 的数字组成——每个数字的上限。对于所有 1 到 m 的 i,有 l_i ≤ r_i。 - 所有测试用例中 s 的长度之和不超过 3 * 10^5。 输出: - 对于每个测试用例,如果存在符合所有条件的密码,则输出 "YES",否则输出 "NO"。