← 返回题目列表

Codeforces · 2053/G

G. 朴素的字符串分割

中文机器翻译题面 查看原题

Cocoly 有一个长度为 $$$m$$$ 的字符串 $$$t$$$,由小写英文字母组成,他想将其拆分为多个部分。当且仅当存在字符串序列 $$$a_1, a_2, \ldots, a_k$$$ 时,他称一对字符串 $$$(x, y)$$$ 美丽,这样:

- $$$t = a_1 + a_2 + \ldots + a_k$$$,其中 $$$+$$$ 表示字符串连接。
- 对于每个 $$$1 \leq i \leq k$$$,至少满足以下条件之一:$$$a_i = x$$$,或 $$$a_i = y$$$。

Cocoly 还有另一个字符串 $$$s$$$,长度为 $$$n$$$,由小写英文字母组成。现在,对于每个 $$$1 \leq i < n$$$,Cocoly 希望您确定字符串对 $$$(s_1s_2 \ldots s_i, \, s_{i+1}s_{i+2} \ldots s_n)$$$ 是否漂亮。

注意:由于输入和输出很大,因此您可能需要针对此问题对其进行优化。

例如,在 C++ 中,在 main() 函数的开头使用以下几行就足够了:

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq m \leq 5 \cdot 10^6$$$) - $$$s$$$ 的长度和 $$$t$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,仅由小写英文字母组成。

每个测试用例的第三行包含一个长度为$$$m$$$的字符串$$$t$$$,仅由小写英文字母组成。

保证所有测试用例的$$$m$$$总和不超过$$$10^7$$$。

输出

对于每个测试用例,输出长度为 $$$n - 1$$$ 的单个二进制字符串 $$$r$$$:对于每个 $$$1 \leq i < n$$$,如果第 $$$i$$$ 对很漂亮,则 $$$r_i=\texttt{1}$$$;否则,$$$r_i=\texttt{0}$$$。不要输出空格。

示例

输入 #1

7
3 5
aba
ababa
4 10
czzz
czzzzzczzz
5 14
dream
dredreamamamam
5 18
tcccc
tcctccccctccctcccc
7 11
abababc
abababababc
7 26
aaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
19 29
bbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbb

输出 #1

11
011
0010
0000
010100
111111
110010001100010011

注意

在第一个测试用例中,$$$s = \tt aba$$$,$$$t = \tt ababa$$$。

- 对于 $$$i = 1$$$:Cocoly 可以拆分 $$$t = \texttt{a} + \texttt{ba} + \texttt{ba}$$$,因此字符串对 $$$(\texttt{a}, \texttt{ba})$$$ 很漂亮。
- 对于 $$$i = 2$$$:Cocoly 可以拆分 $$$t = \texttt{ab} + \texttt{ab} + \texttt{a}$$$,因此字符串对 $$$(\texttt{ab}, \texttt{a})$$$ 很漂亮。

在第二个测试用例中,$$$s = \tt czzz$$$,$$$t = \tt czzzzzczzz$$$。

- 对于$$$i = 1$$$:可以证明,没有解决方案可以使用字符串$$$\texttt{c}$$$和$$$\texttt{zzz}$$$给出$$$t$$$的分区。
- 对于 $$$i = 2$$$:Cocoly 可以将 $$$t$$$ 拆分为 $$$\texttt{cz} + \texttt{zz} + \texttt{zz} + \texttt{cz} + \texttt{zz}$$$。
- 对于 $$$i = 3$$$:Cocoly 可以将 $$$t$$$ 拆分为 $$$\texttt{czz} + \texttt{z} + \texttt{z} + \texttt{z} + \texttt{czz} + \texttt{z}$$$。