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​=a；
• S 2 = a a S_2=\tt aaS2​=aa；
• S 3 = b a b S_3=\tt babS3​=bab；
• S 4 = c a a c S_4=\tt caacS4​=caac；
• S 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

输入 1

aaababcaacd

输出 1

5

输入输出样例 2

输入 2

abacdcaaba

输出 2

2

说明/提示

【样例解释】

• 对于第1 11组样例，已经在题面中进行表述；
• 对于第2 22组样例，S 1 = a S_1=\tt aS1​=a，S 2 = b a S_2=\tt baS2​=ba，S 3 = c d c S_3=\tt cdcS3​=cdc，S 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,…的规则顺序分割成若干段，最后不足的部分单独成段，然后统计这些段中有多少个是回文字符串。

解题步骤：

1. 维护当前段应达到的长度len（初始为 1），以及当前正在构建的段字符串cur。
2. 遍历原字符串S SS的每个字符，逐个拼接到cur中。
3. 当cur的长度等于len时（即达到了当前段的理论长度），或者已经遍历到最后一个字符（即最后一段可能不足），则：
   • 调用chk函数判断cur是否为回文。
   • 如果是回文，答案加一。
   • 清空cur，并将len增加 1，准备下一段。
4. 输出最终统计的答案。

时间复杂度：每个字符被拼接一次，每个段在判断回文时会复制并反转字符串，总字符复制次数等于所有段长度之和，即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∣​），可以接受。

代码实现

#include<bits/stdc++.h>usingnamespacestd;// 判断字符串 s 是否为回文（使用 reverse）boolchk(string s){string t=s;// 复制原串reverse(t.begin(),t.end());// 反转returns==t;// 比较是否相等}intmain(){string S;cin>>S;// 读入原始字符串intn=S.size(),len=1,ans=0;// n:长度, len:当前段预期长度, ans:回文段个数string cur="";// 当前正在构建的段for(inti=0;i<n;++i){// 遍历每个字符cur+=S[i];// 将当前字符拼接到段中// 当段长度达到预期 或 已经到达字符串末尾（最后一段）if(cur.size()==len||i==n-1){if(chk(cur))++ans;// 若是回文则计数cur="";// 清空，准备下一段++len;// 下一段预期长度+1}}cout<<ans<<'\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 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}