1 条题解
-
0
思路分析
1. 任务拆解: 我们要统计一个字符串中所有连续回文子串的数量,包括长度为1的子串。
2. 关键点分析:
- 回文串有奇数长度和偶数长度两种情况,需要分别处理
- 每个单独的字符本身就是一个回文子串
- 使用中心扩展法来寻找回文子串
3. 步骤规划:
- 第一步: 处理多组输入数据。
- 第二步: 统计奇数长度回文子串:
- 以每个字符为中心,向两边扩展
- 如果左右字符相等,就找到一个回文子串,继续扩展
- 如果不相等,停止扩展
- 第三步: 统计偶数长度回文子串:
- 以每两个相邻字符为中心,向两边扩展
- 如果左右字符相等,就找到一个回文子串,继续扩展
- 如果不相等,停止扩展
- 第四步: 输出结果:所有扩展找到的回文子串数 + 单个字符的数量
4. 代码对应:
while(cin>>a)处理多组输入- 第一个
for循环:处理奇数长度回文,以每个字符为中心向两边扩展 - 第二个
for循环:处理偶数长度回文,以每两个字符为中心向两边扩展 if(a[l]==a[r]) s++; else break;检查是否回文,是则计数,否则停止扩展cout<<s+a.size()<<endl;输出结果(扩展找到的回文数 + 单个字符数)
简单理解: 就像在字符串中找"对称点",从每个位置向两边展开,看能形成多少个对称的片段。奇数长度从单个字符展开,偶数长度从两个相同字符展开。
- 1
信息
- ID
- 1533
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 211
- 已通过
- 64
- 上传者