思路:
子串的长度只能为奇数或偶数(长度为1的不算,直接特判)。
对于长度为奇数的子串,,以之间的数为该子串的中心,然后分别向两边扩展,只要碰到一个子串扩展不满足回文的,就退出。对于偶数长度的子串分别以1到n – 1之间的数为左,该数右边的数为右,组成两个数,然后再拿这两个数扩展。
代码:
;LL;const int M = 100009,INF = 0x3fffffff;string str;int n;LL odd(void) {LL o = 0;for(int i = n – 2; i > 0; i–) {for(int j = 1; j <= min(n – i – 1, i); j++) {if(str[i + j] == str[i – j]) o++;else break;}}return o;}LL even(void) {LL e = 0;for(int i = 0; i < n – 1; i++) {for(int j = 0; j <= min(i, n – i – 2); j++) {if(str[i – j] == str[i + j + 1]) e++;else break;}}return e;}int main(void) {while(cin >> str) {//for(int i = 0; i < 5000; i++) str += ‘a’;n = str.size();cout << odd() + even() + n << endl;}return 0;}
你并不一定会从此拥有更美好的人生,