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}$$$。