CF1951E.No Palindromes

Christopher Tin ft. Soweto Gospel Choir - Baba Yetu

ඞ

给定一个由小写拉丁字母组成的字符串 $s$。你需要将该字符串划分为若干个子串，使得每个子串都不是回文串。

$^\dagger$ 一个字符串 $s$ 的划分是一个有序的 $k$ 个字符串 $t_1, t_2, \ldots, t_k$ 的序列，满足 $t_1 + t_2 + \ldots + t_k = s$，其中 $+$ 表示连接操作。

$^\ddagger$ 如果一个字符串 $s$ 从前往后读和从后往前读都相同，则称其为回文串。例如，$\mathtt{racecar}$、$\mathtt{abccba}$ 和 $\mathtt{a}$ 都是回文串，而 $\mathtt{ab}$、$\mathtt{dokibird}$ 和 $\mathtt{kurosanji}$ 不是回文串。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含一个由小写拉丁字母组成的字符串 $s$（$1 \le |s| \le 10^6$）。

保证所有测试用例中字符串长度之和不超过 $10^6$。

对于每个测试用例，如果存在一种划分方式使得每个部分都不是回文串，输出一行 "YES"；否则输出 "NO"。

如果答案为 "YES"，则在第二行输出一个整数 $k$，表示将 $s$ 划分为 $k$ 个部分，每个部分都不是回文串。在第三行输出 $k$ 个字符串 $t_1, t_2, \ldots, t_k$，表示一种满足条件的划分方式。如果有多种划分方式，输出任意一种即可。

在第一个测试用例中，$\mathtt{sinktheyacht}$ 本身就不是回文串，因此划分为 $[\mathtt{sinktheyacht}]$ 是合法的。

在第二个测试用例中，字符串 $s$ 的任意子串都是回文串，因此不存在合法的划分方式。

在第三个测试用例中，另一种合法的划分方式是 $[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$。

由 ChatGPT 4.1 翻译