csp信奥赛C++高频考点专项训练之字符串 --【回文字符串】：小洛的字符串分割

csp信奥赛C高频考点专项训练之字符串 --【回文字符串】小洛的字符串分割题目描述对于一个字符串S SS小洛定义它为回文的当且仅当字符串S SS从左往右读和从右往左读一样例如a b c b a \tt abcbaabcba是回文的而a b c c a \tt abccaabcca不是。小洛现在有一个字符串S SS他想将这个字符串分为若干段段长度分别为1 , 2 , 3 , … 1,2,3,\dots1,2,3,…。具体而言他会先将第一个字符拿出来作为字符串S 1 S_1S1​再将第2 , 3 2,32,3个字符拿出来作为S 2 S_2S2​再将第4 , 5 , 6 4,5,64,5,6个字符拿出来作为S 3 S_3S3​以此类推……最后若还有多余的字符则单独作为一段。例如说对于字符串a a a b a b c a a c d \tt aaababcaacdaaababcaacd会被分为如下的五个字符串S 1 a S_1\tt aS1​aS 2 a a S_2\tt aaS2​aaS 3 b a b S_3\tt babS3​babS 4 c a a c S_4\tt caacS4​caacS 5 d S_5\tt dS5​d字符串a a a b a b c a a c d \tt aaababcaacdaaababcaacd分割出的5 55个字符串都是回文的。小洛想要知道对于读入的字符串S SS这些被分割出来的字符串有多少个是回文的呢输入格式输入一行一个字符串S SS。输出格式输出一个整数表示答案。输入输出样例 1输入 1aaababcaacd输出 15输入输出样例 2输入 2abacdcaaba输出 22说明/提示【样例解释】对于第1 11组样例已经在题面中进行表述对于第2 22组样例S 1 a S_1\tt aS1​aS 2 b a S_2\tt baS2​baS 3 c d c S_3\tt cdcS3​cdcS 4 a a b a S_4\tt aabaS4​aaba其中S 1 S_1S1​与S 3 S_3S3​为回文字符串。【数据范围】假定记号∣ S ∣ |S|∣S∣表示字符串S SS的长度。对于10 % 10\%10%的数据字符串至多包含一种字母对于30 % 30\%30%的数据字符串至多包含两种字母对于70 % 70\%70%的数据∣ S ∣ ≤ 1000 |S|\leq 1000∣S∣≤1000对于所有数据1 ≤ ∣ S ∣ ≤ 10 6 1 \leq |S| \leq 10^61≤∣S∣≤106字符串仅包含英语小写字母。思路分析题目要求将字符串S SS按照长度依次为1 , 2 , 3 , … 1,2,3,\dots1,2,3,…的规则顺序分割成若干段最后不足的部分单独成段然后统计这些段中有多少个是回文字符串。解题步骤维护当前段应达到的长度len初始为 1以及当前正在构建的段字符串cur。遍历原字符串S SS的每个字符逐个拼接到cur中。当cur的长度等于len时即达到了当前段的理论长度或者已经遍历到最后一个字符即最后一段可能不足则调用chk函数判断cur是否为回文。如果是回文答案加一。清空cur并将len增加 1准备下一段。输出最终统计的答案。时间复杂度每个字符被拼接一次每个段在判断回文时会复制并反转字符串总字符复制次数等于所有段长度之和即O ( ∣ S ∣ ) O(|S|)O(∣S∣)因此总体复杂度O ( ∣ S ∣ ) O(|S|)O(∣S∣)满足∣ S ∣ ≤ 10 6 |S| \le 10^6∣S∣≤106的要求。空间复杂度除了输入字符串外仅使用了常数个辅助变量和一个临时段字符串cur最坏情况下cur的长度不超过最大段长度约2 ∣ S ∣ \sqrt{2|S|}2∣S∣​可以接受。代码实现#includebits/stdc.husingnamespacestd;// 判断字符串 s 是否为回文使用 reverseboolchk(string s){string ts;// 复制原串reverse(t.begin(),t.end());// 反转returnst;// 比较是否相等}intmain(){string S;cinS;// 读入原始字符串intnS.size(),len1,ans0;// n:长度, len:当前段预期长度, ans:回文段个数string cur;// 当前正在构建的段for(inti0;in;i){// 遍历每个字符curS[i];// 将当前字符拼接到段中// 当段长度达到预期 或 已经到达字符串末尾最后一段if(cur.size()len||in-1){if(chk(cur))ans;// 若是回文则计数cur;// 清空准备下一段len;// 下一段预期长度1}}coutans\n;return0;}功能分析输入处理从标准输入读取一个仅包含小写字母的字符串S SS长度1 ≤ ∣ S ∣ ≤ 10 6 1 \le |S| \le 10^61≤∣S∣≤106。分段逻辑模拟题目描述的“段长度分别为 1,2,3…”的顺序分割过程。使用变量len记录当前段应该达到的长度cur动态拼接当前段的字符。当cur.size() len时表示已收集满当前段立即处理当i n-1时表示剩余字符不足一段则将最后剩余的字符作为一段处理。回文判断自定义chk函数通过复制字符串并反转后与原串比较简洁地判断是否为回文。虽然复制和反转会带来额外开销但由于每个字符只会被复制一次因为每个字符属于唯一一个段总时间复杂度仍为O ( ∣ S ∣ ) O(|S|)O(∣S∣)。输出输出一个整数表示所有分割段中回文字符串的数量。【完整系列请查看专栏】信奥赛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;}