csp信奥赛C++高频考点专项训练之字符串 --【回文字符串】：回文拼接

csp信奥赛C高频考点专项训练之字符串 --【回文字符串】回文拼接题目描述一个字符串是回文串当且仅当该字符串从前往后读和从后往前读是一样的例如aabaa \texttt{aabaa}aabaa和ccddcc \texttt{ccddcc}ccddcc都是回文串但abcd \texttt{abcd}abcd不是。小杨有n nn个仅包含小写字母的字符串他想请你编写程序判断每个字符串是否由两个长度至少为2 22的回文串前后拼接而成。输入格式第一行包含一个正整数n nn代表字符串数量。接下来n nn行每行一个仅包含小写字母的字符串。输出格式对于每个字符串输出一行如果该字符串由两个长度至少为2 22的回文串前后拼接而成则输出 Yes否则输出 No。输入输出样例 1输入 14 abcd aabbb aaac abcdd输出 1No Yes No No说明/提示样例 1 解释对于第1 , 3 , 4 1,3,41,3,4个字符串都不是由两个长度至少为2 22的回文串前后拼接而成。第2 22个字符串由回文串aa \texttt{aa}aa和bbb \texttt{bbb}bbb前后拼接而成并且两个回文串长度都至少为2 22。数据规模与约定对全部的测试数据保证1 ≤ n ≤ 10 1 \leq n \leq 101≤n≤10且每个字符串的长度均不超过100 100100。分析思路题目要求判断一个字符串是否能被分割成两个长度均至少为 2 的回文子串前后拼接。因为字符串长度不超过 100可以直接暴力枚举所有可能的分割点。分割点i表示前一部分的长度即前i个字符要求2 ≤ i ≤ len-2后一部分长度至少为 2。对于每个分割点分别检查前部分[0, i-1]和后部分[i, len-1]是否为回文串。如果存在任何一个分割点满足条件输出Yes否则输出No。检查回文串采用双指针法时间复杂度 O(len)总时间复杂度 O(n * len²)完全可行。代码实现#includebits/stdc.husingnamespacestd;// 判断字符串 s 中区间 [l, r] 是否为回文串boolcheck(string s,intl,intr){while(lr){// 双指针从两端向中间比较if(s[l]!s[r])returnfalse;// 发现不同字符不是回文l;r--;// 移动指针继续比较}returntrue;// 全部相同是回文串}intmain(){intn;// 字符串个数cinn;// 读入 nwhile(n--){// 循环处理每个字符串string s;// 当前字符串cins;// 读入字符串intlens.size();// 字符串长度boolokfalse;// 标记是否找到合法分割// 枚举分割点 i 表示前部分长度范围 2 ~ len-2前后长度至少为2for(inti2;ilen-2;i){// 检查前部分 [0, i-1] 和后部分 [i, len-1] 是否都是回文if(check(s,0,i-1)check(s,i,len-1)){oktrue;// 找到合法分割break;// 无需继续枚举}}// 根据结果输出 Yes 或 Nocout(ok?Yes:No)\n;}return0;}功能分析功能对输入的每个字符串判断它是否能由两个长度至少为 2 的回文串前后拼接而成。实现方式暴力枚举所有可能的分割点前部分长度从 2 到总长度减 2对每个分割点调用回文判断函数检查前后两部分。回文判断使用双指针法从两端向中间比较字符。时间复杂度每个字符串长度L ≤ 100分割点最多L-3个每个分割点做两次回文判断每次 O(L)故单串最坏 O(L²) ≈ 10⁴ 次操作总 n ≤ 10完全可在 1 秒内完成。空间复杂度仅使用了常数个变量O(1) 额外空间。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}