题目描述
在给出一个字符串 S ，计算 S中有多少连续子串是回文串。
输入
输入包含多组测试数据。每组输入是一个非空字符串，长度不超过3000 。测试数据不超过3000 行。
输出
对于每组输入，输出的回文子串的个数。
样例输入1
aba
aa
样例输出1
4
3
做法1
我们可以通过“枚举回文串中心”并“不断向外扩展”的方式，来找出所有的回文子串。
注意，奇数长度和偶数长度的回文串在处理的方式上存在一些差别，因此可能需要分别统计。
#include <bits/stdc++.h> using namespace std; int main() { string s; while (cin >> s) { int ans = 0; for (int i = 0, len; i < s.size(); ++i) { /* 统计奇数长度的回文串 */ len = 0; while (i - len >= 0 && i + len < s.size() && s[i - len] == s[i + len]) { ++ans; ++len; } /* 统计偶数长度的回文串 */ len = 0; while (i - len >= 0 && i + 1 + len <= s.size() && s[i - len] == s[i + 1 + len]) { ++ans; ++len; } } cout << ans << endl; } return 0; }
