题目解析
* 输入输出:第一行输入整数 nnn 表示字符串数量。随后 nnn 行每行一个仅含小写字母的字符串。对每个字符串,若其能拆分为两个长度均不小于 222 的回文子串首尾拼接而成,则输出 Yes,否则输出 No。
* 数据范围:1≤n≤101 \le n \le 101≤n≤10,单个字符串长度不超过 100100100。数据规模较小,允许 O(L2)O(L^2)O(L2) 的暴力解法(LLL 为字符串长度)。
* 复杂度要求:单串处理复杂度 O(L2)O(L^2)O(L2)(枚举分割点 O(L)O(L)O(L),每次回文判断 O(L)O(L)O(L)),总复杂度 O(n⋅L2)≤10×104=105O(n \cdot L^2) \le 10 \times 10^4 = 10^5O(n⋅L2)≤10×104=105,轻松满足时限。
* 算法知识点:回文串判定、字符串枚举、子串提取
思路解析
1. 长度剪枝:若字符串长度小于 444,则无法分割为两个长度至少为 222 的子串(2+2=42+2=42+2=4),直接判定为 No。
2. 枚举分割点:设分割位置为 iii(表示前 i+1i+1i+1 个字符为第一部分),iii 的取值范围为 [1,L−3][1, L-3][1,L−3](LLL 为串长)。此范围确保:
* 前半部分长度 i+1≥2i+1 \ge 2i+1≥2
* 后半部分长度 L−(i+1)≥2L-(i+1) \ge 2L−(i+1)≥2
3. 回文判定:对每一个分割位置,提取前后两个子串,分别与其反转字符串比较。若两者均为回文(即子串等于其反转),则找到合法拆分,输出 Yes 并提前退出。
4. 终止条件:若枚举完所有可能的分割点均未发现双回文结构,则输出 No。
完整代码