回文子串的个数_统计回文子串的个数

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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; 
}