给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
输入: "abc" 输出: 3 解释: 三个回文子串: "a", "b", "c".
示例 2:
输入: "aaa" 输出: 6 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:
- 输入的字符串长度不会超过1000。
m[i-1]: 表示子串s[0··i-1]的最大回文子串数。s[0··i]的回文子串数包含两部分，一部分是s[0··i-1]的回文子串数，一部分是以s[i]为结尾的回文子串数。
1 int length(char* s, int loc){ 2 int i, j, step, cnt = 0; 3 for(step = loc; step >= 0; --step){ 4 j = loc - step; 5 for(i = j; i <= j + (loc - j) / 2; ++i){ 6 if(s[i] != s[loc - i + j]) 7 break; 8 } 9 if(i > j + (loc - j) / 2) 10 ++cnt; 11 } 12 return cnt; 13 } 14 int countSubstrings(char* s) { 15 int m[1000], i, len = strlen(s); 16 m[0] = 1; 17 for(i = 1; i < len; ++i){ 18 m[i] = m[i-1] + length(s, i); 19 } 20 return m[len-1]; 21 }