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

1、题目描述

 

  1.1、题目

        本题要求统计一个字符串中包含多少个回文子串。首先我们来确定子串的概念：一个字符串的子串，就是指它本身的各个部分。如字符串“aba”的子串有“a”、“b”、“a”、“ab”、“ba”和“aba”。

       再来看回文，回文就是从左读到右和从右读到左都是一样的，长度为1的字符串也是回文。如“a”、“s”、"aa"、“aba”和“aabaa”等都是回文。

      本题在一个字符串中，单个字符也被认为是回文子串，相同的重复的子串也需要计算在内。本题要求判断一个字符串中的所有的子串是否是回文子串。如果用常规方法做，肯定会出现超时错误。这里采用由中心向外扩散的方法去判断一个子串是否是回文子串，如果最中心的子串不是回文，那么，立即终止，不必去判断向外围扩散的子串了，这就大大节约了时间。

      下面以“abaa”为例，讲解由中心向外扩散的方法，如下图所示。

（1）从左往右，钉住最后一个字符。

“abaa”串：先考查中心子串“ba”不是回