回文子串的个数

题目描述

给定一个字符串，计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

输入格式

一个字符串 s，长度不超过 1000。

输出格式

一个正整数，表示 s 有多少个回文子串。

样例输入 #1

aabc

样例输出 #1

5

数据范围

字符串长度不超过 1000。 时间限制：1000MS，内存限制：128MB。

样例解释

一共有 5 个回文子串，分别是 a,a,b,c,aa。

知识点与难度

本题涉及的知识点从属于 GESP 7级（动态规划提高、区间DP），难度等级：Mid。

测试点分布