大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
1、题目描述
1.1、题目
本题要求统计一个字符串中包含多少个回文子串。首先我们来确定子串的概念：一个字符串的子串，就是指它本身的各个部分。如字符串“aba”的子串有“a”、“b”、“a”、“ab”、“ba”和“aba”。
再来看回文，回文就是从左读到右和从右读到左都是一样的，长度为1的字符串也是回文。如“a”、“s”、”aa”、“aba”和“aabaa”等都是回文。
本题在一个字符串中，单个字符也被认为是回文子串，相同的重复的子串也需要计算在内。本题要求判断一个字符串中的所有的子串是否是回文子串。如果用常规方法做，肯定会出现超时错误。这里采用由中心向外扩散的方法去判断一个子串是否是回文子串，如果最中心的子串不是回文，那么，立即终止，不必去判断向外围扩散的子串了，这就大大节约了时间。
下面以“abaa”为例，讲解由中心向外扩散的方法，如下图所示。
（1）从左往右，钉住最后一个字符。
“abaa”串：先考查中心子串“ba”不是回文串，就可以判定“abaa”不是回文子串；
“baa”串：先考查中心子串“baa”不是回文，它是最外子串，不必向外扩散；
“aa”串：考查中心子串中“aa”是回文，它是最外子串，不必向外扩散。
（2）从右边倒数第二个字符往左，钉住第一个字符。
“aba”串：考查中心子串“aba”，是回文，它是最外子串，不必向外扩展；
“ab”串：考查子串“ab”，不是回文，它是最外子串，不必向外扩展；
这样下来，加上单个子串“a”，“b”，“a”，“a”4个，“abaa”中共包含6个回文子串。
1.2、输入描述
输入数据中有多个测试案例。每个案例是一个非空且长度不超过5000的字符串。
处理到文件结尾。
1.3、输出描述
在每行上打印该字符串中回文子串的个数。
1.4、输入样例
aba
aa
1.5、输出样例
4
3
2、C++实现
#include <iostream> using namespace std; int main(int argc, char* argv[]) { char s[5000]; int p, i, Half, Left, Right, Count; while( cin>>s ) { i = strlen(s); Count = 0; //从左到右钉住最后一个 for(p=0; p<=i-1; p++) { Half = ((i-1)-p) / 2; //如果子串是奇数个 if( ((i-1)-p)%2 == 0 ) { Left = p + Half - 1; Right = p + Half + 1; } else { //如果子串是偶数个 Left = p + Half; Right = p + Half + 1; } while(Left >= p) { if( s[Left] == s[Right]) { Count++; //发现了一个回文串 Left--; Right++; } else { //如果不相等，立即终止，由中心向外扩散不可能会有回文串 break; } } } //从右到左钉住第一个 for(p=i-2; p>=1; p--) { Half = p / 2; //如果子串是奇数个 if(p%2 == 0) { Left = Half - 1; Right = Half + 1; } else //如果子串是偶数个 { Left = Half; Right = Half + 1; } while( Left >= 0 ) { if( s[Left] == s[Right] ) { Count++; //发现了一个回文串 Left--; Right++; } else { //如果不相等，立即终止，由中心向外扩散不可能会有回文串 break; } } } printf("%d\n",Count + i); } return 0; }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/181307.html原文链接：https://javaforall.net
